結果
問題 | No.1561 connect x connect |
ユーザー | kotatsugame |
提出日時 | 2021-06-25 23:27:40 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,721 bytes |
コンパイル時間 | 1,592 ms |
コンパイル使用メモリ | 106,160 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-25 08:54:06 |
合計ジャッジ時間 | 5,548 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 6 ms
6,944 KB |
testcase_02 | AC | 80 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,944 KB |
testcase_05 | AC | 3 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,944 KB |
testcase_11 | AC | 6 ms
6,940 KB |
testcase_12 | AC | 18 ms
6,940 KB |
testcase_13 | AC | 81 ms
6,940 KB |
testcase_14 | AC | 395 ms
6,944 KB |
testcase_15 | AC | 398 ms
6,940 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 3 ms
6,944 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | AC | 18 ms
6,940 KB |
testcase_32 | AC | 80 ms
6,944 KB |
testcase_33 | AC | 391 ms
6,940 KB |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
コンパイルメッセージ
main.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 39 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<map> #include<queue> #include<atcoder/modint> using namespace std; using mint=atcoder::modint1000000007; #include<vector> template<typename T> T lagrange_interpolation(const vector<T>&y,long long x_) { int N=y.size(); if(N==0)return T(0); if(x_<N)return y[x_]; vector<T>fac(N),invfac(N); fac[0]=1; for(int i=1;i<N;i++)fac[i]=fac[i-1]*i; invfac[N-1]=1/fac[N-1]; for(int i=N-1;i--;)invfac[i]=invfac[i+1]*(i+1); vector<T>L(N),R(N); T x=x_; L[0]=1; for(int i=1;i<N;i++)L[i]=L[i-1]*(x-(i-1)); R[N-1]=1; for(int i=N-1;i--;)R[i]=R[i+1]*(x-(i+1)); T ret=0; for(int i=0;i<N;i++) { T now=L[i]*R[i]*invfac[i]*invfac[N-i-1]*y[i]; if(N-i&1)ret+=now; else ret-=now; } return ret; } int N; int pr[18]; int find(int u){return u!=pr[u]?pr[u]=find(pr[u]):u;} int usd[18],usdid[18],usdtm; main() { cin>>N; if(N==9)return 0;//N=9 vector<vector<int> >inv(1,vector<int>(N,-1)); map<vector<int>,int>mp; mp[inv[0]]=0; vector<pair<int,int> >E; queue<int>P;P.push(0); while(!P.empty()) { int u=P.front();P.pop(); for(int i=0;i<1<<N;i++) { usdtm++; for(int j=0;j<N;j++) { int id=inv[u][j]; if(id<0)pr[j]=-1; else { if(usd[id]<usdtm) { usd[id]=usdtm; usdid[id]=j; } pr[j]=usdid[id]; } } for(int j=0;j<N;j++)pr[j+9]=i>>j&1?j+9:-1; for(int j=0;j<N;j++) { if(pr[j]>=0&&pr[j+9]>=0) { int x=find(j),y=find(j+9); if(x!=y)pr[y]=x; } } for(int j=0;j<N-1;j++) { if((i>>j&3)==3) //pr[j+9]>=0&&pr[j+1+9]>=0) { int x=find(j+9),y=find(j+1+9); if(x!=y)pr[y]=x; } } vector<int>now(N,-1); usdtm++; int id=0; for(int j=0;j<N;j++)if(i>>j&1) { int x=find(j+9); if(usd[x]<usdtm) { usd[x]=usdtm; usdid[x]=id++; } now[j]=usdid[x]; } if(i>0) { bool ok=true; for(int j=0;j<N;j++)if(inv[u][j]>=0) { int x=find(j); if(usd[x]<usdtm) { ok=false; break; } } if(!ok)continue; } if(mp.find(now)==mp.end()) { int sz=mp.size(); mp[now]=sz; inv.push_back(now); P.push(sz); } id=mp[now]; if(u!=0&&id==0) { int ok=-1; for(int j=0;j<N;j++)if(inv[u][j]>=0) { if(ok==-1)ok=inv[u][j]; else if(ok!=inv[u][j])ok=-2; } if(ok==-2)continue; id=-1; } E.push_back(make_pair(u+1,id+1)); } } E.push_back(make_pair(0,0)); const int n=2188+1; vector<mint>T(n); T[1]=1; vector<mint>y(n+5); for(int i=0;i<n+5;i++) { y[i]=T[0]; vector<mint>nT(n); for(pair<int,int>e:E) { nT[e.second]+=T[e.first]; } T=nT; } long M;cin>>M; cout<<lagrange_interpolation(y,M+1).val()<<endl; }