結果

問題 No.2255 Determinant Sum
ユーザー pockynypockyny
提出日時 2023-03-29 06:26:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,107 bytes
コンパイル時間 2,497 ms
コンパイル使用メモリ 88,480 KB
実行使用メモリ 7,952 KB
最終ジャッジ日時 2023-10-20 23:54:38
合計ジャッジ時間 6,809 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 2 ms
4,348 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

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 pw(ll a,ll x){
    ll ret = 1;
    while(x){
        if(x&1) (ret *= a) %= mod;
        (a *= a) %= mod; x /= 2;
    }
    return ret;
}

ll inve(ll x){return pw(x,mod - 2);}
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;
            for(k=0;k<n;k++){
                (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;
    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]*fi[i]%mod*fi[d - 1 - i]%mod;
        if(s>0) (ans += x) %= mod; 
        else (ans += mod - x) %= mod;
        s *= -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;
        if(mod!=2){
            cout << 0 << "\n";
        }else{
            solve();
            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];
            }
            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)*inve(2)%mod;
            cout << interpolation(f,val) << "\n";
            // for(i=0;i<n;i++) cout  << f[i] << " ";
            // cout << "\n";
        }
    }
}
0