QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546475 | #9116. DRD String | ucup-team1766 | WA | 0ms | 3516kb | C++17 | 1.1kb | 2024-09-04 03:58:52 | 2024-09-04 03:58:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
long long binpow(long long a, long long b) {
if (b == 0) {
return 1;
}
long long c = binpow(a, b / 2);
if (b % 2 == 0) {
return c * c % MOD;
} else {
return c * c % MOD * a % MOD;
}
}
long long modinv(long long a) {
return binpow(a, MOD - 2);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<long long> powM(2 * N + 1);
powM[0] = 1;
for (int i = 1; i <= 2 * N; i++) {
powM[i] = powM[i - 1] * M % MOD;
}
vector<long long> dp(N + 1);
vector<long long> sum(N + 1);
dp[1] = M;
sum[1] = dp[1] * modinv(powM[2]) % MOD;
for (int i = 2; i <= N; i++) {
dp[i] = powM[i] - powM[i] * sum[i / 2] % MOD + MOD;
dp[i] %= MOD;
sum[i] = sum[i - 1] + dp[i] * modinv(powM[2 * i]) % MOD;
sum[i] %= MOD;
}
long long res = (powM[N] - dp[N] + MOD) % MOD;
cout << res << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3516kb
input:
6 2
output:
44
result:
wrong answer 1st words differ - expected: '40', found: '44'