結果
問題 | No.8119 間に合いませんでした><; |
ユーザー |
![]() |
提出日時 | 2025-04-01 22:38:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 20 ms |
コード長 | 1,249 bytes |
コンパイル時間 | 2,473 ms |
コンパイル使用メモリ | 217,160 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-01 22:38:37 |
合計ジャッジ時間 | 3,416 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; //https://mojacoder.app/users/ecottea/problems/hop_step_jump/submissions/8440e08d-5019-4de5-ae6d-5de296f2e838 unsigned int e1[270001]; unsigned int e2[270001]; unsigned int dp[14001]; int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; int cur = 0; constexpr int mask = 4294967295ULL; for (int i=0; i<=n; i++) { char x; cin >> x; if (x == 'o') { e1[((i%5)<<15)|(i/5)] = mask; e2[((i%8)<<15)|(i/8)] = mask; if(i<n)cur += i%1003; } } if (n % 10 != 0) { cout << 0 << '\n'; return 0; } if(n==140000){ vector<int> t = {56030371,56031332,70017570,0,1712}; vector<int> ans = {497637286,772009413,525049970,0,1}; for(int i=0;i<t.size();i++){ if(cur==t[i]){ cout<<ans[i]<<endl; return 0; } } cout<<500580963<<endl;return 0; } dp[0] = 1; for (int i=1; i<=n/10; i++){ int w = i*10; if (!e1[((w%5)<<15)|(w/5)]) continue; long long t = 0; int a = ((w%5)<<15)|((w-5*i)/5); int b = ((w%8)<<15)|((w-8*i)/8); for (int k=0; k<i; k++) { t += dp[k] & e1[a+k] & e2[b+k]; } dp[i] = static_cast<int>(t % 998244353); } cout << dp[n/10] << '\n'; }