結果
| 問題 | No.1561 connect x connect |
| コンテスト | |
| ユーザー |
 kotatsugame
|
| 提出日時 | 2021-06-25 23:36:28 |
| 言語 | C++14 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,697 bytes |
| 記録 | |
| コンパイル時間 | 1,494 ms |
| コンパイル使用メモリ | 123,928 KB |
| 実行使用メモリ | 13,656 KB |
| 最終ジャッジ日時 | 2026-03-11 17:50:20 |
| 合計ジャッジ時間 | 15,613 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 WA * 16 |
コンパイルメッセージ
main.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main()
| ^~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/vector:67,
from main.cpp:2:
In function '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = atcoder::static_modint<1000000007>*; _ForwardIterator = atcoder::static_modint<1000000007>*]',
inlined from '_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _Sentinel, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = atcoder::static_modint<1000000007>*; _Sentinel = atcoder::static_modint<1000000007>*; _ForwardIterator = atcoder::static_modint<1000000007>*; _Tp = atcoder::static_modint<1000000007>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_uninitialized.h:637:37,
inlined from 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = atcoder::static_modint<1000000007>; _Alloc = std::allocator<atcoder::static_modint<1000000007> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/vector.tcc:257:35,
inlined from 'int main()' at main.cpp:147:5:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_uninitialized.h:273:31: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' writing between 1 and 8756 bytes into a region of size 0 overflows the destination [-Wstringop-overflow=]
273 | __builtin_memcpy(std::__niter_base(__result),
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
274 | std::__niter_base(__first),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~
275 | __n * sizeof(_ValT));
| ~~~~~~~~~~~~~~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/inc
ソースコード
#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;
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;
}