結果

問題 No.2255 Determinant Sum
ユーザー pockynypockyny
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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";
        }
    }
}
0