結果

問題 No.612 Move on grid
コンテスト
ユーザー kotatsugame
提出日時 2020-03-11 06:07:17
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,188 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 756 ms
コンパイル使用メモリ 66,688 KB
実行使用メモリ 84,224 KB
最終ジャッジ日時 2024-11-15 23:57:51
合計ジャッジ時間 53,694 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 WA * 2 TLE * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~

ソースコード

diff #
raw source code 

#include<iostream>
using namespace std;
int T;
int a,b,c,d,e;
long mod=1e9+7;
long comb[501][501],combsum[501][501];
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
main()
{
	cin>>T>>a>>b>>c>>d>>e;
	comb[0][0]=1;
	combsum[0][0]=1;
	for(int i=1;i<=T;i++)
	{
		comb[i][0]=comb[i][i]=1;
		for(int j=1;j<i;j++)comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%mod;
		combsum[i][0]=1;
		for(int j=1;j<=i;j++)combsum[i][j]=(comb[i][j]+combsum[i][j-1])%mod;
	}
	long ans=0;
	for(int i=0;i<=T;i++)for(int ii=0;ii<=T-i;ii++)
	{
		int x=i-ii;
		int Tr=T-i-ii;
		long XW=comb[T][i]*comb[T-i][ii]%mod;
		for(int j=0;j<=Tr;j++)for(int jj=0;jj<=Tr-j;jj++)
		{
			int y=j-jj;
			long XYW=XW*comb[Tr][j]%mod*comb[Tr-j][jj]%mod;
			int Z=Tr-j-jj;
			int D=d-a*x-b*y+c*Z;
			int E=e-a*x-b*y+c*Z;
			int L=0,R=Z;
			if(c==0);
			else if(c>0)
			{
				L=max(L,D/(2*c));
				if(2*c*L<D)L++;
				R=min(R,E/(2*c));
				if(2*c*R>E)R--;
			}
			else
			{
				L=max(L,E/(-2*c));
				if(2*c*L>E)L++;
				R=min(R,D/(-2*c));
				if(2*c*R<D)R--;
			}
			if(L<=R&&D<=2*c*L&&2*c*R<=E)
			{
				long t=(combsum[Z][R]+mod-(L==0?0:combsum[Z][L-1]))%mod;
				(ans+=t*XYW)%=mod;
			}
		}
	}
	cout<<ans<<endl;
}
0