結果

問題 No.1474 かさまＪ
ユーザー 37zigen37zigen
提出日時 2021-02-27 22:06:14
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 3,232 bytes
コンパイル時間 3,061 ms
コンパイル使用メモリ 80,264 KB
実行使用メモリ 120,856 KB
最終ジャッジ日時 2024-04-10 15:51:28
合計ジャッジ時間 6,731 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 142 ms
63,132 KB
testcase_01 AC 141 ms
55,904 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 制約の確認

import java.util.*;
class Main
{
    public static void main(String[] args)
    {
        new Main().run();
    }
    
    final long MOD=(long)1e9+7;
    
    long[]  fac=new long[100000];
    long[] ifac=new long[100000];
    long[] inv=new long[100000];
    {
    	fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1;
    	for (int i=2;i<fac.length;++i) {
    		fac[i]=i*fac[i-1]%MOD;
    		inv[i]=MOD-(MOD/i)*inv[(int)(MOD%i)]%MOD;
    		ifac[i]=inv[i]*ifac[i-1]%MOD;
    	}
    }
    
    long comb(int n,int k) {
    	if (n<0||k<0||n-k<0) return 0;
    	return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
    }
    
    long exact(int N,int Mp,int Mq,int L,int[] S) {
    	long[][][] f=new long[N+1][Mp+1][Mq+1];
    	f[0][0][0]=1;
    	for (int i=0;i+1<=N;++i) {
    		for (int p=0;p<=Mp;++p) {
	    		for (int q=0;q<=Mq;++q) {
	    			if (f[i][p][q]==0) continue;
	    			for (int dp=0;dp<=Mp;++dp) {
		    			for (int dq=0;dq<=Mq;++dq) {
		    				if (dp+dq<L&&dq>0) continue;
		    				if (dq>S[i]) continue;
		    				int np=p+dp;
		    				int nq=q+dq;
		    				if (np>Mp||nq>Mq) continue;
		    				f[i+1][np][nq]=(f[i+1][np][nq]+f[i][p][q])%MOD;
		    			}	
	    			}
	    		}
    		}
    	}
    	long ans=0;
    	for (int i=0;i<=Mq;++i) ans=(ans+f[N][Mp][i])%MOD;
    	return ans;
    }
    
    void rnd() {
    	Random rnd=new Random(10);
    	while(true) {
	    	int N=20;
	    	int L=20;
	    	int Mp=1+rnd.nextInt(L);
	    	int Mq=rnd.nextInt(L);
	    	int[] S=new int[N];
	    	for (int i=0;i<N;++i) {
	    		S[i]=rnd.nextInt(L);
	    	}
	    	long a=solve(N,Mp,Mq,L,S);
	    	long b=exact(N,Mp,Mq,L,S);
	    	if (a!=b)
	    	{
	    		tr(N,Mp,Mq,L,S);
	    		tr(a,b);
	    		return;
	    	}
	    }
    }
    
    void run()
    {
        Scanner sc=new Scanner(System.in);    
        int N=sc.nextInt();
        int Mp=sc.nextInt();
        int Mq=sc.nextInt();
        int L=sc.nextInt();
        int[] S=new int[N];
        for (int i=0;i<N;++i) {
            S[i]=sc.nextInt();
            assert(0<=S[i]&&S[i]<L);
    	}
    	assert(1<=N&&N<=40);
    	assert(1<=Mp&&Mp<=20000);
    	assert(0<=Mq&&Mq<=20000);
    	assert(1<=L&&L<=10000);
    	
        System.out.println(exact(N,Mp,Mq,L,S));
    }
    
   long solve(int N,int Mp,int Mq,int L,int[] S) {
        long[][] dp=new long[N+1][Mq+1];
        dp[0][0]=1;
        // x+x^2+x^3+..+x^s=(x-x^(s+1))/(1-x)
        for (int i=0;i<N;++i) {
        	for (int n=N-1;n>=0;--n) {
        		for (int q=0;q<=Mq;++q) {
	        		if (q+1<=Mq) dp[n+1][q+1]=(dp[n+1][q+1]+dp[n][q])%MOD;
	        		if (q+S[i]+1<=Mq) dp[n+1][q+S[i]+1]=(dp[n+1][q+S[i]+1]+MOD-dp[n][q])%MOD;
        		}
        		for (int q=0;q<=Mq;++q) dp[n+1][q]%=MOD;
        	}
        }
        for (int n=0;n<=N;++n) {
        	for (int t=0;t<n;++t) {
        		for (int q=1;q<=Mq;++q) {
        			dp[n][q]=(dp[n][q-1]+dp[n][q])%MOD;
        		}
        	}
        }
        long ans=0;
        for (int n=0;n<=N;++n) {
        	for (int q=0;q<=Mq;++q) {
        		if (n*L-q>Mp) continue;
        		ans=(ans+comb(N-1+Mp-(n*L-q),N-1)*dp[n][q]%MOD)%MOD;
        	}
        }
        return ans;
   }
    
    void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}
0