結果
問題 | No.310 2文字しりとり |
ユーザー | 👑 kmjp |
提出日時 | 2016-01-06 23:34:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,429 ms / 6,000 ms |
コード長 | 2,371 bytes |
コンパイル時間 | 1,527 ms |
コンパイル使用メモリ | 150,392 KB |
実行使用メモリ | 194,308 KB |
最終ジャッジ日時 | 2023-08-25 02:39:02 |
合計ジャッジ時間 | 11,244 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,732 KB |
testcase_01 | AC | 2 ms
5,452 KB |
testcase_02 | AC | 2 ms
5,480 KB |
testcase_03 | AC | 2 ms
5,632 KB |
testcase_04 | AC | 2 ms
5,468 KB |
testcase_05 | AC | 2 ms
5,600 KB |
testcase_06 | AC | 2 ms
5,464 KB |
testcase_07 | AC | 2 ms
5,764 KB |
testcase_08 | AC | 2 ms
5,448 KB |
testcase_09 | AC | 2 ms
5,584 KB |
testcase_10 | AC | 2 ms
5,564 KB |
testcase_11 | AC | 2 ms
5,708 KB |
testcase_12 | AC | 2 ms
5,492 KB |
testcase_13 | AC | 2 ms
5,484 KB |
testcase_14 | AC | 2 ms
5,488 KB |
testcase_15 | AC | 2 ms
5,712 KB |
testcase_16 | AC | 2 ms
5,652 KB |
testcase_17 | AC | 2 ms
5,528 KB |
testcase_18 | AC | 4 ms
9,984 KB |
testcase_19 | AC | 4 ms
7,868 KB |
testcase_20 | AC | 7 ms
9,948 KB |
testcase_21 | AC | 940 ms
194,184 KB |
testcase_22 | AC | 991 ms
194,144 KB |
testcase_23 | AC | 1,389 ms
194,124 KB |
testcase_24 | AC | 1,429 ms
194,308 KB |
testcase_25 | AC | 1,018 ms
194,212 KB |
testcase_26 | AC | 755 ms
80,396 KB |
testcase_27 | AC | 831 ms
99,052 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<to;x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N,M; int A[4040],B[4040]; int in[4040],out[4040]; int st,en; ll fact[8080]; int self[4040]; ll mo=1000000007; int id[4040],rid[4040]; int edge[4040][4040]; ll mat[4040][4040]; ll modpow(ll a, ll n = mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll det_mo(int N) { int x,y,z; ll ret=1; FOR(y,N) FOR(z,N) mat[y][z]=((mat[y][z]%mo)+mo)%mo; FOR(x,N) { vector<int> V; for(y=x;y<N;y++) if(mat[y][x]) V.push_back(y); if(V.size()==0) return 0; y=V[rand()%V.size()]; if(y!=x) { FOR(z,N) swap(mat[x][z],mat[y][z]); ret=(mo-ret)%mo; } ret=ret*mat[x][x]%mo; ll rev=modpow(mat[x][x]); FOR(z,N) mat[x][z]=rev*mat[x][z]%mo; for(y=x+1;y<N;y++) if(mat[y][x]) { rev=mat[y][x]; for(z=x;z<N;z++) if(mat[x][z]) mat[y][z]=(mat[y][z]+mo*mo-mat[x][z]*rev)%mo; } } return ret; } void solve() { int i,j,k,l,r,x,y; string s; srand(time(NULL)); fact[0]=1; FOR(i,8000) fact[i+1]=fact[i]*(i+1)%mo; cin>>N>>M; FOR(i,N) { FOR(j,N) edge[i][j]=-1; in[i]=out[i]=N; edge[i][i]=N-1; } FOR(i,M) { cin>>x>>y; x--,y--; out[x]--; in[y]--; edge[x][y]++; edge[y][y]--; } x=0; st=en=-1; FOR(i,N) { if(in[i]==0 && out[i]==0) id[i]=-1; else id[i]=x, rid[x]=i, x++; if(abs(in[i]-out[i])>1) return _P("0\n"); if(in[i]==out[i]+1) { if(en!=-1) return _P("0\n"); en=i; } if(out[i]==in[i]+1){ if(st!=-1) return _P("0\n"); st=i; } } if(x==0 || x==1) return _P("1\n"); ll pat=(N*N-M)%mo; N=x; if(st>=0) { // odd in[st]++; out[en]++; edge[en][st]--; edge[st][st]++; pat=1; } FOR(i,N) pat = pat*fact[in[rid[i]]-1]%mo; FOR(i,N) FOR(j,N) mat[i][j]=edge[rid[i]][rid[j]]; cout<<(pat*det_mo(N-1)%mo)<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }