Submit Info #2682

Problem Lang User Status Time Memory
Determinant of Matrix cpp kyoprofriends AC 336 ms 2.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.50 MiB
example_01 AC 6 ms 0.52 MiB
example_02 AC 6 ms 0.49 MiB
lowrank_max_random_00 AC 311 ms 2.38 MiB
lowrank_max_random_01 AC 286 ms 2.30 MiB
lowrank_max_random_02 AC 332 ms 2.38 MiB
lowrank_max_random_03 AC 281 ms 2.37 MiB
lowrank_max_random_04 AC 309 ms 2.28 MiB
max_random_00 AC 328 ms 2.38 MiB
max_random_01 AC 332 ms 2.30 MiB
max_random_02 AC 336 ms 2.39 MiB
max_random_03 AC 323 ms 2.33 MiB
max_random_04 AC 326 ms 2.38 MiB
perm_max_random_00 AC 317 ms 2.38 MiB
perm_max_random_01 AC 319 ms 2.38 MiB
perm_max_random_02 AC 325 ms 2.40 MiB
perm_max_random_03 AC 310 ms 2.26 MiB
perm_max_random_04 AC 315 ms 2.38 MiB
random_00 AC 23 ms 0.68 MiB
random_01 AC 29 ms 0.75 MiB
random_02 AC 9 ms 0.57 MiB
random_03 AC 29 ms 0.72 MiB
random_04 AC 5 ms 0.51 MiB

#include <stdio.h> #define rep(i,l,r)for(ll i=(l);i<(r);i++) #define ll long long ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;} #define invp(a,p)pom(a,p-2,p) #define MOD 998244353 int det(ll*mat,int size,int mod){ //modはprime int swapcnt=0; rep(i,0,size){ int piv=i; while(piv<size&&!mat[piv*size+i])piv++; if(piv==size)return 0; //swap if(piv!=i){ swapcnt++; rep(j,i,size){ll temp=mat[i*size+j];mat[i*size+j]=mat[piv*size+j];mat[piv*size+j]=temp;} } int invpiv=invp(mat[i*size+i],mod); rep(k,i+1,size){ int coe=(-mat[k*size+i]*invpiv%mod+mod)%mod; rep(j,i,size)mat[k*size+j]=(mat[k*size+j]+mat[i*size+j]*coe)%mod; } } ll ans=1; rep(i,0,size)ans=ans*mat[i*size+i]%mod; return swapcnt%2?mod-ans:ans; } ll a[300000]; int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%lld",a+i*n+j); printf("%d\n",det(a,n,MOD)); }