結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
ユーザー piyoko_212piyoko_212
提出日時 2015-12-27 00:57:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,257 ms / 4,000 ms
コード長 6,863 bytes
コンパイル時間 1,320 ms
コンパイル使用メモリ 77,996 KB
実行使用メモリ 43,456 KB
最終ジャッジ日時 2024-09-19 07:14:30
合計ジャッジ時間 5,359 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,257 ms
43,456 KB
testcase_01 AC 1,245 ms
43,368 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:201:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  201 |         scanf("%lld%d%d",&n,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
namespace NTT{
	long long extgcd(long long a,long long b,long long&x,long long&y){
		for(long long u=y=1,v=x=0;a;){
			long long q=b/a;swap(x-=q*u,u);swap(y-=q*v,v);swap(b-=q*a,a);
		}
		return b;
	}
	long long mod_inv(long long a,long long m){
		long long x,y;
		extgcd(a,m,x,y);
		return (m+x%m)%m;
	}
	long long mod_pow(long long a,long long b,long long m){
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%m;
			b/=2;
			a=a*a%m;
		}
		return ret;
	}
	map<pair<int,vector<long long> >, vector<long long> > memo;
	template<int mod,int primitive_root> class NTT{
		public:
		int get_mod()const{return mod;}
		void _ntt(vector<long long>&a,int sign){
			const int n=a.size();
			const int g=3;
			int h=(int)mod_pow(g,(mod-1)/n,mod);
			if(sign==-1)h=(int)mod_inv(h,mod);
			int i=0;
			for(int j=1;j<n-1;j++){
				for(int k=n>>1;k>(i^=k);k>>=1);
				if(j<i)swap(a[i],a[j]);
			}
			for(int m=1;m<n;m*=2){
				const int m2=2*m;
				const long long base=mod_pow(h,n/m2,mod);
				long long w=1;
				for(int x=0;x<m;x++){
					for(int s=x;s<n;s+=m2){
						long long u=a[s];
						long long d=a[s+m]*w%mod;
						a[s]=u+d;
						if(a[s]>=mod)a[s]-=mod;
						a[s+m]=u-d;
						if(a[s+m]<0)a[s+m]+=mod;
					}
					w=w*base%mod;
				}
			}
			for(int i=0;i<a.size();i++)if(a[i]<0)a[i]+=mod;
		}
		void ntt(vector<long long>&input){
			_ntt(input,1);
		}
		void intt(vector<long long>&input){
			_ntt(input,-1);
			const int n_inv=mod_inv(input.size(),mod);
			for(int i=0;i<input.size();i++)input[i]=input[i]*n_inv%mod;
		}
		vector<long long>convolution(const vector<long long>&a,const vector<long long>&b){
			int ntt_size=1;
			while(ntt_size<a.size()+b.size())ntt_size*=2;
			vector<long long>_a=a,_b=b;
			_a.resize(ntt_size);
			_b.resize(ntt_size);
			if(memo.count(make_pair(mod,a)))_a=memo[make_pair(mod,a)];
			else{
				ntt(_a);
		//		memo[make_pair(mod,a)]=_a;
			}
			if(memo.count(make_pair(mod,_b)))_b=memo[make_pair(mod,b)];
			else{
				ntt(_b);
		//		memo[make_pair(mod,b)]=_b;
			}
			for(int i=0;i<ntt_size;i++){
				(_a[i]*=_b[i])%=mod;
			}
			intt(_a);
			return _a;
		}
	};
	long long garner(vector<pair<long long,long long> > mr,long long mod){
		mr.push_back(make_pair(mod,0));
		vector<long long>coffs(mr.size(),1);
		vector<long long>constants(mr.size(),0);
		for(int i=0;i<mr.size()-1;i++){
			long long v=(mr[i].second-constants[i])*mod_inv(coffs[i],mr[i].first)%mr[i].first;
			if(v<0)v+=mr[i].first;
			for(int j=i+1;j<mr.size();j++){
				(constants[j]+=coffs[j]*v)%=mr[j].first;
				(coffs[j]*=mr[i].first)%=mr[j].first;
			}
		}
		return constants[mr.size()-1];
	}
	typedef NTT<167772161,3> NTT_1;
	typedef NTT<469762049,3> NTT_2;
	typedef NTT<1224736769,3> NTT_3;
	/*vector<long long>int32mod_convolution(vector<long long>a,vector<long long>b,int mod){
		for(int i=0;i<a.size();i++)a[i]%=mod;
		for(int i=0;i<b.size();i++)b[i]%=mod;
		NTT_1 ntt1;
		NTT_2 ntt2;
		NTT_3 ntt3;
		vector<long long>x=ntt1.convolution(a,b);
		vector<long long>y=ntt2.convolution(a,b);
		vector<long long>z=ntt3.convolution(a,b);
		vector<long long>ret(x.size());
		vector<pair<long long,long long> >mr(3);
		for(int i=0;i<x.size();i++){
			mr[0].first=ntt1.get_mod(),mr[0].second=x[i];
			mr[1].first=ntt2.get_mod(),mr[1].second=y[i];
			mr[2].first=ntt3.get_mod(),mr[2].second=z[i];
			ret[i]=garner(mr,mod);
		}
		return ret;
	}*/
	vector<long long> int32mod_convolution(vector<long long>a,vector<long long>b,int mod){
		for(int i=0;i<a.size();i++)a[i]%=mod;
		for(int i=0;i<b.size();i++)b[i]%=mod;
		NTT_1 ntt1;
		NTT_2 ntt2;
		NTT_3 ntt3;
		vector<long long>x=ntt1.convolution(a,b);
		vector<long long>y=ntt2.convolution(a,b);
		vector<long long>z=ntt3.convolution(a,b);
		const long long m1=ntt1.get_mod();
		const long long m2=ntt2.get_mod();
		const long long m3=ntt3.get_mod();
		const long long m1_inv_m2=mod_inv(m1,m2);
		const long long m12_inv_m3=mod_inv(m1*m2,m3);
		const long long m12_mod=m1*m2%mod;
		vector<long long>ret(x.size());
		for(int i=0;i<x.size();i++){
			long long v1=(y[i]-x[i])*m1_inv_m2%m2;
			if(v1<0)v1+=m2;
			long long v2=(z[i]-(x[i]+m1*v1)%m3)*m12_inv_m3%m3;
			if(v2<0)v2+=m3;
			long long constants3=(x[i]+m1*v1+m12_mod*v2)%mod;
			if(constants3<0)constants3+=mod;
			ret[i]=constants3;
		}
		return ret;
	}
}
long long mod=1000000007;
int s[]={2,3,5,7,11,13};
int t[]={4,6,8,9,10,12};
long long U[8000];
long long S[4000];
long long T[4000];
int dp[8][310][4000];
long long ul=8000;
vector<long long>g;
vector<long long>h;

vector<long long> calc(long long t){
//	printf("%lld\n",t);
	if(t<ul){
		vector<long long>ret(8000);
		ret[t]=1;
		return ret;
	}
	vector<long long>chi=calc(t/2);
	vector<long long>na(8000);
	for(int i=0;i<8000;i++){
		na[i]=chi[i];
	}
	vector<long long>f=NTT::int32mod_convolution(na,na,mod);
	if(t%2){
		for(int i=16383;i>0;i--)f[i]=f[i-1];
		f[0]=0;
	}
	f.resize(16010);
	vector<long long>_f=f;
	reverse(_f.begin(),_f.end());
	_f.resize(8010);
	vector<long long>q=NTT::int32mod_convolution(_f,h,mod);
	q.resize(8010);
	reverse(q.begin(),q.end());
	vector<long long>r=NTT::int32mod_convolution(q,g,mod);
//	printf("%d %d\n",r.size(),f.size());
	for(int i=0;i<r.size();i++)r[i]=(mod-r[i])%mod;
	for(int i=0;i<8000;i++)r[i]=(r[i]+f[i])%mod;
	r.resize(8000);
//	printf("%lld: \n",t);
//	for(int i=0;i<r.size();i++)if(r[i])printf("%d: %lld\n",i,r[i]);
	return r;
}
int main(){
	long long n;
	int a,b;
	scanf("%lld%d%d",&n,&a,&b);
	dp[0][0][0]=1;
	for(int i=0;i<6;i++){
		for(int j=0;j<=a;j++){
			for(int k=0;k<3950;k++){
				if(dp[i][j][k]==0)continue;
				dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
				if(j<a)dp[i][j+1][k+s[i]]=(dp[i][j+1][k+s[i]]+dp[i][j][k])%mod;
			}
		}
	}
	for(int i=0;i<4000;i++)S[i]=dp[6][a][i];
	for(int i=0;i<8;i++)for(int j=0;j<310;j++)for(int k=0;k<4000;k++)dp[i][j][k]=0;
	dp[0][0][0]=1;
	for(int i=0;i<6;i++){
		for(int j=0;j<=b;j++){
			for(int k=0;k<3950;k++){
				if(dp[i][j][k]==0)continue;
				dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
				if(j<b)dp[i][j+1][k+t[i]]=(dp[i][j+1][k+t[i]]+dp[i][j][k])%mod;
			}
		}
	}
	for(int i=0;i<4000;i++)T[i]=dp[6][b][i];
	for(int i=0;i<4000;i++)for(int j=0;j<4000;j++){
		U[i+j]=(U[i+j]+S[i]*T[j])%mod;
	}
	g.resize(8001);
	g[8000]=1;
	for(int i=1;i<8000;i++){
		g[8000-i]=(mod-U[i])%mod;
	}
	vector<long long>_g=g;
	reverse(_g.begin(),_g.end());
	h.push_back(1);
	int L=1;
	while(L<8010){
		vector<long long>h2=NTT::int32mod_convolution(h,h,mod);
		vector<long long>tg=_g;
		tg.resize(L*2);
		h2=NTT::int32mod_convolution(h2,tg,mod);
		h2.resize(L*2);
		for(int i=0;i<L*2;i++)h2[i]=(mod-h2[i])%mod;
		for(int i=0;i<L;i++)h2[i]=(h2[i]+h[i]*2)%mod;
		h=h2;
		L*=2;
	}
	h.resize(8010);
	vector<long long> ans=calc(n+7999);
	long long ret=0;
	for(int i=0;i<8000;i++){
		ret=(ret+ans[i])%mod;
	}
	printf("%lld\n",ret);
}
0