結果
問題 |
No.2907 Business Revealing Dora Tiles
|
ユーザー |
|
提出日時 | 2024-05-31 22:21:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,656 bytes |
コンパイル時間 | 11,617 ms |
コンパイル使用メモリ | 260,060 KB |
実行使用メモリ | 13,888 KB |
最終ジャッジ日時 | 2024-09-23 10:53:51 |
合計ジャッジ時間 | 25,737 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 TLE * 1 -- * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/modint> using namespace atcoder; using mint=modint998244353; vector nim_prod_table(256, vector<unsigned long long>(256)); vector<unsigned long long> nim_inv_table(256); void nim_prod_precalc() { nim_prod_table[0][0]=0; nim_prod_table[0][1]=0; nim_prod_table[1][0]=0; nim_prod_table[1][1]=1; for(int d=0;d<3;++d){ int p=1<<d; for(int a=0;a<(1<<(2*p));++a){ for(int b=(1<<p);b<(1<<(2*p));++b){ unsigned long long a_h=a>>p; unsigned long long a_l=a-(a_h<<p); unsigned long long b_h=b>>p; unsigned long long b_l=b-(b_h<<p); unsigned long long al_bl=nim_prod_table[a_l][b_l]; unsigned long long ahl_bhl=nim_prod_table[a_h^a_l][b_h^b_l]; unsigned long long ah_bh=nim_prod_table[a_h][b_h]; unsigned long long ah_bh_h=nim_prod_table[ah_bh][1ULL<<(p-1)]; nim_prod_table[a][b]=nim_prod_table[b][a]=((al_bl^ahl_bhl)<<p)^(al_bl^ah_bh_h); } } } } unsigned long long nim_product(unsigned long long a, unsigned long long b, int p=64) { if(p==8){ return nim_prod_table[a][b]; } p/=2; unsigned long long a_h=a>>p; unsigned long long a_l=a-(a_h<<p); unsigned long long b_h=b>>p; unsigned long long b_l=b-(b_h<<p); unsigned long long al_bl=nim_product(a_l, b_l, p); unsigned long long ahl_bhl=nim_product(a_h^a_l, b_h^b_l, p); unsigned long long ah_bh=nim_product(a_h, b_h, p); unsigned long long ah_bh_h=nim_product(ah_bh, 1ULL<<(p-1), p); return ((al_bl^ahl_bhl)<<p)^(al_bl^ah_bh_h); } void nim_inv_precalc() { for(int i=0;i<256;++i){ for(int j=0;j<256;++j){ if(nim_product(i, j, 8)==1){ nim_inv_table[i]=j; break; } } } } unsigned long long nim_inv(unsigned long long a, int p=64) { if(p==8){ return nim_inv_table[a]; } p/=2; unsigned long long a_h=a>>p; unsigned long long a_l=a-(a_h<<p); unsigned long long half_inv=nim_inv(nim_product(a_h^a_l, a_l)^nim_product(nim_product(a_h, a_h), 1ULL<<(p-1)), p); return (nim_product(half_inv, a_h)<<p)^nim_product(half_inv, a_h^a_l); } int gauss(int r, int c, vector<vector<unsigned long long>> & m, vector<bool> & exists) { int rank=0; for(int i=0;i<c;++i){ if(!exists[i]){ continue; } int pivot=-1; for(int j=rank;j<r;++j){ if(m[j][i]>0){ pivot=j; break; } } if(pivot==-1){ continue; } swap(m[pivot], m[rank]); auto inv=nim_inv(m[rank][i]); m[rank][i]=1; for(int k=rank+1;k<c;++k){ if(!exists[k]){ continue; } m[rank][k]=nim_product(m[rank][k], inv); } for(int j=rank+1;j<r;++j){ auto factor=m[j][i]; m[j][i]=0; for(int k=rank+1;k<c;++k){ if(!exists[k]){ continue; } m[j][k]^=nim_product(m[rank][k], factor); } } ++rank; if(rank==r){ break; } } return rank; } int main(void) { nim_prod_precalc(); nim_inv_precalc(); int n,t; cin >> n >> t; vector h(t, vector<unsigned long long>(n)); for(int i=0;i<t;++i){ for(int j=0;j<n;++j){ cin >> h[i][j]; --h[i][j]; } } mint ans=0; vector<bool> exists(n); auto m=h; for(unsigned int s=0;s<(unsigned int)(1<<n);++s){ int count=popcount(s); if(count==0){ if(n%2>0){ --ans; } else { ++ans; } continue; } if(count==1){ if(n%2>0){ ++ans; } else { --ans; } continue; } for(int i=0;i<n;++i){ exists[i]=((s&(1<<i))>0); } m=h; int rank=gauss(t, n, m, exists); if(n%2>0){ if(count%2>0){ ans+=mint(932051910).pow(count-rank); } else { ans-=mint(932051910).pow(count-rank); } } else { if(count%2>0){ ans-=mint(932051910).pow(count-rank); } else { ans+=mint(932051910).pow(count-rank); } } } cout << ans.val() << endl; return 0; }