#include <vector> #include <cstdio> #include <stack> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <unordered_set> #include <unordered_map> #include <set> #include <cstring> #include <bitset> #include <iostream> #include <queue> #include <iomanip> #include <complex> using namespace std; #define ALL(x) x.begin(), x.end() #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin()) #define FOR(i, a, b) for(int i =(a); i <=(b); ++i) #define RE(i, n) FOR(i, 1, n) #define RED(i, n) FORD(i, n, 1) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REP(i, n) for(int i = 0;i <(n); ++i) #define REPD(i, n) FORD(i, n-1,0) const int maxn = 36, maxm = 1010; const long long mod = 998244353, inf = 1000000004000000004ll; int n,m, s[maxm][2], res[maxn], a[maxn], il1, ans, tb[36]; int dfs(int akt){ if(akt == -1) { return 1; } if(tb[s[akt][0]] == 0 && tb[s[akt][1]] == 1) { swap(tb[s[akt][0]], tb[s[akt][1]]); auto pom = dfs(akt - 1); swap(tb[s[akt][0]], tb[s[akt][1]]); return pom ^ dfs(akt - 1); } if(tb[s[akt][0]] == tb[s[akt][1]]){ return dfs(akt - 1); } return 0; } void solve() { cin>>n>>m; REP(i, m)cin>>s[i][0]>>s[i][1]; if(n >= 17) { RE(dl, n) { ans = 0; RE(po, n - dl + 1) { RE(i, n) { tb[i] = i >= po && i < po + dl; } ans ^= dfs(m - 1); } cout << ans << " "; } } else { REP(i, (1<<(n))){ auto pom = i; il1 = 0; RE(j, n){ a[j] = pom % 2; pom /= 2; if(a[j])il1 ++; } REP(j, m)if(a[s[j][0]] && !a[s[j][1]])swap(a[s[j][0]], a[s[j][1]]); vector<int> po; po.push_back(a[1]); FOR(j, 2, n)if(a[j] != a[j - 1])po.push_back(a[j]); if(po.size() < 3) { res[il1]++; } if(po.size() == 3){ if(po[1] == 1){ res[il1]++; } } } RE(i, n)cout<<(res[i]) % 2<<" "; // cout<<"\n"; } cout<<"\n"; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); int tt = 1; // cin >> tt; while (tt--) { solve(); } 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <vector> #include <cstdio> #include <stack> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <unordered_set> #include <unordered_map> #include <set> #include <cstring> #include <bitset> #include <iostream> #include <queue> #include <iomanip> #include <complex> using namespace std; #define ALL(x) x.begin(), x.end() #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin()) #define FOR(i, a, b) for(int i =(a); i <=(b); ++i) #define RE(i, n) FOR(i, 1, n) #define RED(i, n) FORD(i, n, 1) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REP(i, n) for(int i = 0;i <(n); ++i) #define REPD(i, n) FORD(i, n-1,0) const int maxn = 36, maxm = 1010; const long long mod = 998244353, inf = 1000000004000000004ll; int n,m, s[maxm][2], res[maxn], a[maxn], il1, ans, tb[36]; int dfs(int akt){ if(akt == -1) { return 1; } if(tb[s[akt][0]] == 0 && tb[s[akt][1]] == 1) { swap(tb[s[akt][0]], tb[s[akt][1]]); auto pom = dfs(akt - 1); swap(tb[s[akt][0]], tb[s[akt][1]]); return pom ^ dfs(akt - 1); } if(tb[s[akt][0]] == tb[s[akt][1]]){ return dfs(akt - 1); } return 0; } void solve() { cin>>n>>m; REP(i, m)cin>>s[i][0]>>s[i][1]; if(n >= 17) { RE(dl, n) { ans = 0; RE(po, n - dl + 1) { RE(i, n) { tb[i] = i >= po && i < po + dl; } ans ^= dfs(m - 1); } cout << ans << " "; } } else { REP(i, (1<<(n))){ auto pom = i; il1 = 0; RE(j, n){ a[j] = pom % 2; pom /= 2; if(a[j])il1 ++; } REP(j, m)if(a[s[j][0]] && !a[s[j][1]])swap(a[s[j][0]], a[s[j][1]]); vector<int> po; po.push_back(a[1]); FOR(j, 2, n)if(a[j] != a[j - 1])po.push_back(a[j]); if(po.size() < 3) { res[il1]++; } if(po.size() == 3){ if(po[1] == 1){ res[il1]++; } } } RE(i, n)cout<<(res[i]) % 2<<" "; // cout<<"\n"; } cout<<"\n"; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); int tt = 1; // cin >> tt; while (tt--) { solve(); } return 0; } |