結果
| 問題 | No.3716 Keep it Integer |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-11 10:49:20 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 21 ms / 2,000 ms |
| + 341µs | |
| コード長 | 1,107 bytes |
| 記録 | |
| コンパイル時間 | 4,561 ms |
| コンパイル使用メモリ | 381,956 KB |
| 実行使用メモリ | 9,908 KB |
| 最終ジャッジ日時 | 2026-11-11 10:49:39 |
| 合計ジャッジ時間 | 9,010 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge4_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 47 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, x;
cin >> n >> x;
vector<ll> A(n + 2);
A[0] = x;
for (ll i = 1; i <= n; i++) cin >> A[i];
// i以降で最初にA[j]!=1となる位置
vector<ll> nxt(n + 2, n + 1);
for (ll i = n; i >= 1; i--) {
nxt[i] = (A[i] == 1 ? nxt[i + 1] : i);
}
vector<mint> dp(n + 1), S(n + 2);
// 後ろからDP
for (ll v = n; v >= 0; v--) {
ll a = A[v];
ll j = nxt[v + 1];
// 割り算可能な位置を調べる
while (j <= n && a % A[j] == 0) {
a /= A[j];
j = nxt[j + 1];
}
if (j == n + 1) {
// 最後まで割り算できる
dp[v] = S[v + 1] + 1;
} else {
// jで初めて割り算できなくなる
dp[v] = S[v + 1] - S[j + 1];
}
S[v] = dp[v] + S[v + 1];
}
cout << dp[0].val() << '\n';
}