結果

問題 No.1474 かさまＪ
ユーザー se1ka2
提出日時 2021-04-09 23:00:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,928 bytes
コンパイル時間 730 ms
コンパイル使用メモリ 77,028 KB
実行使用メモリ 169,668 KB
最終ジャッジ日時 2024-06-25 06:45:36
合計ジャッジ時間 2,819 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <functional>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

long long modpow(long long x, long long n){
    long long  res = 1;
    long long mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

struct Combination
{
    int maxn;
    std::vector<long long> fact;
    std::vector<long long> ifact;
    
    Combination(int maxn) : maxn(maxn){
        fact.resize(maxn + 1);
        ifact.resize(maxn + 1);
        fact[0] = 1;
        for(int i = 1; i <= maxn; i++) fact[i] = fact[i - 1] * i % MOD;
        ifact[maxn] = modpow(fact[maxn], MOD - 2);
        for(int i = maxn - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
    }

    long long com(int n, int k){
        if(n < 0 || k > n || k < 0) return 0;
        if(k == n || k == 0) return 1;
        return (fact[n] * ifact[k] % MOD) * ifact[n - k] % MOD;
    }
};

ll dp[42][42][20002];

int main()
{
    int n, mp, mq, l;
    cin >> n >> mp >> mq >> l;
    int s[42];
    for(int i = 0; i < n; i++) cin >> s[i];
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            for(int k = 0; k <= mq; k++) dp[i][j][k] = dp[i - 1][j][k];
        }
        for(int j = 1; j <= i; j++){
            ll d = dp[i - 1][j - 1][0];
            for(int k = 1; k <= mq; k++){
                dp[i][j][k] = (dp[i][j][k] + d) % MOD;
                d = (d + dp[i - 1][j - 1][k]) % MOD;
                if(k - s[i - 1] >= 0) d = (d + MOD - dp[i - 1][j - 1][k - s[i - 1]]) % MOD;
            }
        }
    }
    Combination com(mq + mp + n);
    ll ans = 0;
    for(int j = 0; j <= n; j++){
        for(int k = 0; k <= mq; k++){
            ll x = mp + k - j * l;
            ans = (ans + dp[n][j][k] * com.com(x + n - 1, n - 1)) % MOD;
        }
    }
    cout << ans << endl;
}
0