結果
問題 | No.2772 Appearing Even Times |
ユーザー |
|
提出日時 | 2024-05-31 22:19:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,887 ms / 4,000 ms |
コード長 | 1,647 bytes |
コンパイル時間 | 1,379 ms |
コンパイル使用メモリ | 102,060 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 23:53:36 |
合計ジャッジ時間 | 20,747 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream>#include <vector>#include <cstring>using namespace std;const long long inf = (1LL << 61) - 1;const int mod = 998244353;int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);string n;cin >> n;vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(2, vector<long long>(1024, 0)));dp[0][0][0] = 1;for (int i = 0; i < n.size(); ++i) {vector<vector<vector<long long>>> e(2, vector<vector<long long>>(2, vector<long long>(1024, 0)));for (int lessflag = 0; lessflag < 2; ++lessflag) {for (int zeroflag = 0; zeroflag < 2; ++zeroflag) {for (int bit = 0; bit < 1024; ++bit) {for (int x = 0; x < 10; ++x) {if (lessflag == 0 && x > n[i] - '0') continue;int tlessflag = lessflag | (x < n[i] - '0');int tzeroflag = zeroflag | (x > 0);if (tzeroflag == 0) {e[tlessflag][tzeroflag][bit] += dp[lessflag][zeroflag][bit];e[tlessflag][tzeroflag][bit] %= mod;} else {e[tlessflag][tzeroflag][bit ^ (1 << x)] += dp[lessflag][zeroflag][bit];e[tlessflag][tzeroflag][bit ^ (1 << x)] %= mod;}}}}}dp = e;}int c = 0;for (char v : n) {c ^= 1 << (v - '0');}if (c == 0) {dp[1][1][0] += 1;}cout << dp[1][1][0] % mod << "\n";return 0;}