QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #233003 | #7647. 树哈希 | cy1999 | 8 | 0ms | 4076kb | C++20 | 837b | 2023-10-31 09:40:32 | 2023-10-31 09:40:32 |
answer
#include <bits/stdc++.h>
using namespace std;
struct fastmod {
typedef unsigned long long u64;
typedef __uint128_t u128;
int m;
u64 b;
fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
int reduce(u64 a) {
u64 q = ((u128)a * b) >> 64;
int r = a - q * m;
return r < m ? r : r - m;
}
} z(2);
int n, q, mod;
int main() {
scanf("%d%d%d", &n, &q, &mod);
z = fastmod(mod);
for (int i = 1; i <= n; ++i) {
if (i == 1) printf("%d\n", q);
else if (i == 2) printf("%d\n", z.reduce(1ll * q * q));
else if (i == 3) printf("%d\n", z.reduce(2ll * q % mod * q % mod * q % mod + 1ll * q * q % mod));
else if (i == 4) printf("%d\n", z.reduce(6ll * q % mod * q % mod * q % mod * q % mod + 9ll * q % mod * q % mod * q % mod + 1ll * q % mod * q % mod));
else puts("0");
}
return 0;
}
详细
Subtask #1:
score: 8
Acceptable Answer
Test #1:
score: 8
Acceptable Answer
time: 0ms
memory: 3672kb
input:
100 910342260 935929297
output:
910342260 816177711 569226551 514707635 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
points 0.080 You got 8 pts!
Test #2:
score: 8
Acceptable Answer
time: 0ms
memory: 3784kb
input:
100 222959056 947643239
output:
222959056 358599927 365062242 287299555 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
points 0.080 You got 8 pts!
Test #3:
score: 8
Acceptable Answer
time: 0ms
memory: 4076kb
input:
100 135352674 235854343
output:
135352674 116843515 129198122 128256418 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
points 0.080 You got 8 pts!
Test #4:
score: 8
Acceptable Answer
time: 0ms
memory: 3784kb
input:
100 538608644 566215339
output:
538608644 365236991 134179965 39370099 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
points 0.080 You got 8 pts!
Test #5:
score: 8
Acceptable Answer
time: 0ms
memory: 3796kb
input:
100 56831820 281897771
output:
56831820 213573518 5338712 114481529 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
points 0.080 You got 8 pts!