結果

問題 No.1561 connect x connect
コンテスト
ユーザー kotatsugame
提出日時 2021-06-25 23:27:40
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main()
      | ^~~~

ソースコード

diff #
raw source code 

#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;
}
0