結果
問題 |
No.1964 sum = length
|
ユーザー |
![]() |
提出日時 | 2022-06-06 15:14:50 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 891 bytes |
コンパイル時間 | 1,581 ms |
コンパイル使用メモリ | 141,800 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 04:39:18 |
合計ジャッジ時間 | 3,481 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; ll MOD = 998244353; int main() { int N; cin >> N; int L = 2 * N - 1; ll dp[N + 1][L + 1]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; ll C[L + 10]; memset(C, 0, sizeof(C)); int len = 0; int base = 10; int v = 1; while (v - len <= L) { C[v - len]++; ++v; if (v % base == 0) { len++; base *= 10; } } for (int i = 0; i < N; ++i) { for (int j = 0; j <= L; ++j) { for (int k = 1; k <= L; ++k) { int nj = j + k; if (nj > L) continue; dp[i + 1][nj] += dp[i][j] * C[k]; dp[i + 1][nj] %= MOD; } } } cout << dp[N][L] << endl; return 0; }