結果
問題 | No.2255 Determinant Sum |
ユーザー |
![]() |
提出日時 | 2023-03-29 06:46:00 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,354 bytes |
コンパイル時間 | 4,164 ms |
コンパイル使用メモリ | 115,340 KB |
最終ジャッジ日時 | 2025-02-11 18:58:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 16 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> using namespace std; typedef long long ll; ll mod; ll inve(ll x){return x;} ll det(vector<vector<ll>> a){ int i,j,k,n = a.size(); ll ret = 1; // for(i=0;i<n;i++){ // for(j=0;j<n;j++){ // if(a[i][j]<0) a[i][j] += mod; // if(a[i][j]>=mod) (a[i][j]) %= mod; // } // } for(i=0;i<n;i++){ int piv = -1; for(j=i;j<n;j++){ if(a[j][i]!=0){ piv = j; break; } } if(piv==-1) break; swap(a[piv],a[i]); // if(piv!=i) ret *= -1; for(j=i + 1;j<n;j++){ // ll x = a[j][i]*inve(a[i][i])%mod; ll x = (a[j][i]*inve(a[j][i]))&1; for(k=0;k<n;k++){ (a[j][k] += mod - (a[i][k]*x)&1) &= 1; // (a[j][k] += mod - a[i][k]*x%mod) %= mod; } } } // if(ret<0) ret += mod; // for(i=0;i<n;i++) (ret *= a[i][i]) %= mod; for(i=0;i<n;i++) ret *= a[i][i]; return ret; } const int MX = 110; ll f[MX],inv[MX],fi[MX]; void solve(){ inv[1] = 1; for(int i=2;i<MX;i++){ inv[i] = mod - (mod/i)*inv[mod%i]%mod; } f[0] = fi[0] = 1; for(int i=1;i<MX;i++){ f[i] = f[i-1]*i%mod; fi[i] = fi[i-1]*inv[i]%mod; } } ll nck(ll n, ll k){ if(n<0 || k<0 || n<k) return 0; return f[n]*fi[k]%mod*fi[n-k]%mod; } ll interpolation(vector<ll> &v,ll N){ //given v[0] = f(z),v[1] = f(z + 1),...v[d - 1] = f(z + d - 1) // output f(N) const int z = 0; //可変 int d = v.size(); // vector<ll> pref_sum(d + 1),suff_sum(d + 1); //分子 // pref_sum[0] = suff_sum[d] = 1; // for(int i=1;i<=d;i++) pref_sum[i] = (N + 2*mod - z - i + 1)%mod*pref_sum[i - 1]%mod; // for(int i=d - 1;i>=0;i--) suff_sum[i] = (N + 2*mod - z - i)%mod*suff_sum[i + 1]%mod; ll ans = 0; ll s = 1; for(int i=d - 1;i>=0;i--){ // ll x = v[i]*pref_sum[i]%mod*suff_sum[i + 1]%mod*fi[i]%mod*fi[d - 1 - i]%mod; // ll x = v[i]*fi[i]%mod*fi[d - 1 - i]%mod; // ll x = (v[i]*fi[i]*fi[d - 1 - i])&1; // cout << v[i] << " " << fi[i] << " " << fi[d - 1 - i] << endl; // if(s>0) (ans += x) %= mod; // else (ans += mod - x) %= mod; // s *= -1; (ans += v[i]) &= 1; } return ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t){ t--; int i,j,n; cin >> n >> mod; vector<vector<ll>> a(n),b(n); for(i=0;i<n;i++){ a[i].resize(n); b[i].resize(n); for(j=0;j<n;j++) cin >> a[i][j]; } if(mod!=2){ cout << 0 << "\n"; }else{ solve(); vector<ll> f(n); for(int k=0;k<n;k++){ for(i=0;i<n;i++) b[i] = a[i]; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(b[i][j]==-1) b[i][j] = k; } } f[k] = det(b); } ll val = (mod - 1); cout << interpolation(f,val) << "\n"; // for(i=0;i<n;i++) cout << f[i] << " "; // cout << "\n"; } } }