結果

問題 No.1474 かさまＪ
ユーザー 37zigen37zigen
提出日時 2021-02-27 22:05:09
言語 Java21
(openjdk 21)
結果
AC  
実行時間 635 ms / 2,500 ms
コード長 3,232 bytes
コンパイル時間 2,359 ms
コンパイル使用メモリ 79,740 KB
実行使用メモリ 64,136 KB
最終ジャッジ日時 2024-04-10 15:51:19
合計ジャッジ時間 9,230 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 144 ms
56,088 KB
testcase_01 AC 135 ms
56,220 KB
testcase_02 AC 159 ms
56,260 KB
testcase_03 AC 133 ms
55,996 KB
testcase_04 AC 134 ms
55,956 KB
testcase_05 AC 383 ms
59,716 KB
testcase_06 AC 206 ms
59,760 KB
testcase_07 AC 136 ms
55,976 KB
testcase_08 AC 143 ms
56,008 KB
testcase_09 AC 393 ms
59,880 KB
testcase_10 AC 230 ms
59,460 KB
testcase_11 AC 139 ms
56,096 KB
testcase_12 AC 146 ms
56,108 KB
testcase_13 AC 485 ms
64,136 KB
testcase_14 AC 299 ms
59,872 KB
testcase_15 AC 277 ms
59,820 KB
testcase_16 AC 231 ms
60,112 KB
testcase_17 AC 296 ms
59,864 KB
testcase_18 AC 508 ms
64,020 KB
testcase_19 AC 635 ms
64,028 KB
testcase_20 AC 575 ms
64,060 KB
権限があれば一括ダウンロードができます

ソースコード

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(solve(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