結果
問題 | No.1474 かさまJ |
ユーザー | chocorusk |
提出日時 | 2021-04-09 22:44:53 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 98 ms / 2,500 ms |
コード長 | 1,971 bytes |
コンパイル時間 | 3,492 ms |
コンパイル使用メモリ | 189,288 KB |
実行使用メモリ | 44,888 KB |
最終ジャッジ日時 | 2023-09-07 12:20:32 |
合計ジャッジ時間 | 5,167 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
44,716 KB |
testcase_01 | AC | 15 ms
44,652 KB |
testcase_02 | AC | 15 ms
44,640 KB |
testcase_03 | AC | 14 ms
44,644 KB |
testcase_04 | AC | 14 ms
44,688 KB |
testcase_05 | AC | 47 ms
44,672 KB |
testcase_06 | AC | 21 ms
44,732 KB |
testcase_07 | AC | 15 ms
44,888 KB |
testcase_08 | AC | 15 ms
44,688 KB |
testcase_09 | AC | 61 ms
44,692 KB |
testcase_10 | AC | 17 ms
44,684 KB |
testcase_11 | AC | 15 ms
44,748 KB |
testcase_12 | AC | 14 ms
44,736 KB |
testcase_13 | AC | 66 ms
44,736 KB |
testcase_14 | AC | 30 ms
44,652 KB |
testcase_15 | AC | 21 ms
44,660 KB |
testcase_16 | AC | 16 ms
44,728 KB |
testcase_17 | AC | 32 ms
44,716 KB |
testcase_18 | AC | 82 ms
44,644 KB |
testcase_19 | AC | 94 ms
44,640 KB |
testcase_20 | AC | 98 ms
44,732 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint1000000007; mint dp[2][41][40040], dps[2][41][40040]; mint f[2000010], invf[2000010]; void fac(int n){ f[0]=1; for(ll i=1; i<=n; i++) f[i]=f[i-1]*i; invf[n]=f[n].inv(); for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); } mint comb(int x, int y){ if(!(0<=y && y<=x)) return 0; return f[x]*invf[y]*invf[x-y]; } int main() { int n, mp, mq, l; cin>>n>>mp>>mq>>l; int s[44]; for(int i=0; i<n; i++) cin>>s[i]; dp[0][0][0]=1; for(int i=1; i<=mq+1; i++) dps[0][0][i]=1; for(int i=0; i<n; i++){ for(int j=0; j<=i+1; j++){ for(int k=0; k<=mq; k++){ dp[(i+1)&1][j][k]=0; } } for(int j=0; j<=i; j++){ for(int k=0; k<=mq; k++){ dp[(i+1)&1][j][k]+=dp[i&1][j][k]; dp[(i+1)&1][j+1][k]+=dps[i&1][j][k]-dps[i&1][j][max(0, k-s[i])]; } } for(int j=0; j<=i+1; j++){ dps[(i+1)&1][j][0]=0; for(int k=0; k<=mq; k++){ dps[(i+1)&1][j][k+1]=dps[(i+1)&1][j][k]+dp[(i+1)&1][j][k]; } } } fac(100010); mint ans=0; for(int i=0; i<=mq; i++){ for(int j=0; j<=n; j++){ if(l*j-i<0) continue; ans+=dp[n&1][j][i]*comb(mp-l*j+i+n-1, n-1); } } cout<<ans.val()<<endl; return 0; }