QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #233002 | #7647. 树哈希 | cy1999 | 6 | 1ms | 3724kb | C++20 | 789b | 2023-10-31 09:39:24 | 2023-10-31 09:39:25 |
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 * q * q + 1ll * q * q));
else if (i == 4) printf("%d\n", z.reduce(6ll * q * q % mod * q % mod * q % mod + 9ll * q * q % mod * q + 1ll * q * q % mod));
else puts("0");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Acceptable Answer
Test #1:
score: 6
Acceptable Answer
time: 1ms
memory: 3612kb
input:
100 910342260 935929297
output:
910342260 816177711 130801583 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.060 You got 6 pts!
Test #2:
score: 6
Acceptable Answer
time: 0ms
memory: 3724kb
input:
100 222959056 947643239
output:
222959056 358599927 24644650 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.060 You got 6 pts!
Test #3:
score: 6
Acceptable Answer
time: 0ms
memory: 3604kb
input:
100 135352674 235854343
output:
135352674 116843515 133814470 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.060 You got 6 pts!
Test #4:
score: 6
Acceptable Answer
time: 0ms
memory: 3656kb
input:
100 538608644 566215339
output:
538608644 365236991 6521316 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.060 You got 6 pts!
Test #5:
score: 6
Acceptable Answer
time: 0ms
memory: 3692kb
input:
100 56831820 281897771
output:
56831820 213573518 33489479 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.060 You got 6 pts!