#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
const ll LINF = 1e18;
const int INF = 1e9;
ll solve(const vector<pii> &moves, ll node, int m) {
if (m == 0) {
return 1;
}
m = m - 1;
auto &move = moves[m];
ll a_mask = (1L << move.first);
ll b_mask = (1L << move.second);
bool is_a_set = (a_mask & node) != 0;
bool is_b_set = (b_mask & node) != 0;
if (!(is_a_set ^ is_b_set)) {
return solve(moves, node, m);
}
if (is_a_set && !is_b_set) {
return 0;
}
return solve(moves, (node & ~b_mask) | a_mask, m) + solve(moves, node, m);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pii> moves(m);
for (int i = 0; i < m; ++i) {
cin >> moves[i].first >> moves[i].second;
--moves[i].first;
--moves[i].second;
}
vector<int> cnt(n);
for (int i = 0; i < n; ++i) {
ll mask = 0;
for (int j = i; j < n; ++j) {
mask |= (1L << j);
ll res = solve(moves, mask, m);
cnt[j - i] += res;
// cerr << mask << ' ' << res << '\n';
}
}
for (int i = 0; i < n; ++i) {
cout << cnt[i] % 2 << ' ';
}
cout << endl;
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; const ll LINF = 1e18; const int INF = 1e9; ll solve(const vector<pii> &moves, ll node, int m) { if (m == 0) { return 1; } m = m - 1; auto &move = moves[m]; ll a_mask = (1L << move.first); ll b_mask = (1L << move.second); bool is_a_set = (a_mask & node) != 0; bool is_b_set = (b_mask & node) != 0; if (!(is_a_set ^ is_b_set)) { return solve(moves, node, m); } if (is_a_set && !is_b_set) { return 0; } return solve(moves, (node & ~b_mask) | a_mask, m) + solve(moves, node, m); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<pii> moves(m); for (int i = 0; i < m; ++i) { cin >> moves[i].first >> moves[i].second; --moves[i].first; --moves[i].second; } vector<int> cnt(n); for (int i = 0; i < n; ++i) { ll mask = 0; for (int j = i; j < n; ++j) { mask |= (1L << j); ll res = solve(moves, mask, m); cnt[j - i] += res; // cerr << mask << ' ' << res << '\n'; } } for (int i = 0; i < n; ++i) { cout << cnt[i] % 2 << ' '; } cout << endl; return 0; } |
English