結果

問題 No.1474 かさまＪ
コンテスト
ユーザー 37zigen
提出日時 2021-02-27 21:37:35
言語 Java
(openjdk 23)
結果
AC  
実行時間 598 ms / 2,500 ms
コード長 3,069 bytes
コンパイル時間 2,307 ms
コンパイル使用メモリ 79,716 KB
実行使用メモリ 53,036 KB
最終ジャッジ日時 2024-10-02 18:04:49
合計ジャッジ時間 9,327 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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()
    {
//    	rnd();
        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();
        }
        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