結果
問題 | No.8046 yukicoderの過去問 |
ユーザー |
|
提出日時 | 2019-02-22 19:50:38 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,942 ms / 2,000 ms |
コード長 | 1,570 bytes |
コンパイル時間 | 11,516 ms |
コンパイル使用メモリ | 270,388 KB |
最終ジャッジ日時 | 2025-01-06 21:31:09 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 |
ソースコード
#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" using namespace std; using ll = long long int; #define repeat(cnt,l) for(auto cnt=decltype(l)();(cnt)<(l);++(cnt)) #define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt)) // const int MD = 1000000007; int N, K; int X[100010]; namespace CaseGenerator { void case1() { K = 100000; N = 50000; repeat(i, N) X[i] = i * 2 + 1; } void case2() { K = 100000; N = 66666; repeat(i, 33333) X[i * 2] = i * 3 + 1, X[i * 2 + 1] = i * 3 + 2; } } void input() { cin >> K >> N; repeat(i, N) scanf("%d", X + i); } // int dp[100010]; int f[100010]; int solve() { fill(dp, dp + K + 1, 0); fill(f, f + K + 1, 0); repeat(i, N) f[X[i]] = 1; dp[0] = 1; repeat(k, K) { const int v = dp[k]; repeat(i, K - k + 1) { dp[i + k] += v * f[i]; dp[i + k] -= MD*(dp[i + k] >= MD); } } return dp[K]; } int solve_nyan(){ fill(dp, dp + K + 1, 0); dp[0] = 1; repeat(k, K){ repeat(i, N){ if (k + X[i] <= K) dp[k+X[i]] = (dp[k+X[i]] + dp[k]) % MD; } } return dp[K]; } void test(){ CaseGenerator::case1(); K = 20000; assert(solve() == solve_nyan()); CaseGenerator::case2(); K = 31415; assert(solve() == solve_nyan()); } int main() { //test(); // CaseGenerator::case1(); input(); cout << solve() << endl; //cout << solve_nyan() << endl; return 0; }