QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #767310 | #8834. Formal Fring | forgotmyhandle | AC ✓ | 53ms | 24844kb | C++14 | 879b | 2024-11-20 20:30:01 | 2024-11-20 20:30:18 |
Judging History
answer
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
int n;
int dp[2000005], g[2000005], h[2000005];
signed main() {
ios::sync_with_stdio(false); cout.tie(0);
cin >> n;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = (dp[i - 1] + ((i & 1) ? 0 : dp[i >> 1])) % P;
h[i] = (((i & (i + 1)) == 0) ? __builtin_popcountll(i) : h[i >> 1]);
}
for (int i = 1; i <= 20; i++) {
g[i] = dp[(1 << i) - 1];
for (int j = 1; j < i; j++)
g[i] = (g[i] + (P - g[j]) * dp[(1 << (i - j)) - 1]) % P;
}
for (int i = 1, x = -1; i <= n; i++) {
int tmp = 0;
x += ((i & (i - 1)) == 0);
for (int j = 1; j <= h[i]; j++)
tmp += g[j] * dp[i ^ (((1 << j) - 1) << (x - j + 1))] % P;
cout << tmp % P << " ";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7616kb
input:
10
output:
1 1 2 1 1 3 6 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 7620kb
input:
70
output:
1 1 2 1 1 3 6 1 1 2 2 5 5 11 26 1 1 2 2 4 4 6 6 11 11 16 16 27 27 53 166 1 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 37 37 48 48 64 64 80 80 107 107 134 134 187 187 353 1626 1 1 2 2 4 4 6
result:
ok 70 numbers
Test #3:
score: 0
Accepted
time: 53ms
memory: 24844kb
input:
1000000
output:
1 1 2 1 1 3 6 1 1 2 2 5 5 11 26 1 1 2 2 4 4 6 6 11 11 16 16 27 27 53 166 1 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 37 37 48 48 64 64 80 80 107 107 134 134 187 187 353 1626 1 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60 74 74 94 94 114 114 140 140 166 166 203 203 240 240 288 288 336 336 400 ...
result:
ok 1000000 numbers
Extra Test:
score: 0
Extra Test Passed