QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72613 | #5031. 核 | Chinese_zjc_ | 70 | 1997ms | 160344kb | C++14 | 3.1kb | 2023-01-17 09:05:23 | 2023-01-17 09:06:00 |
Judging History
answer
// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
unsigned MOD;
struct mint
{
unsigned v;
mint(unsigned v_ = 0) : v(v_) {}
mint operator-() const { return v ? MOD - v : *this; }
mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
mint &operator*=(const mint &X) { return v = 1llu * v * X.v % MOD, *this; }
mint &operator/=(const mint &X) { return *this *= X.inv(); }
mint pow(long long B) const
{
B %= MOD - 1;
if (B < 0)
B += MOD - 1;
mint res = 1, A = *this;
while (B)
{
if (B & 1)
res *= A;
B >>= 1;
A *= A;
}
return res;
}
mint inv() const { return pow(MOD - 2); }
friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
explicit operator bool() const { return v; }
} pw3[32769], pW3[32769], pwq[32769], pWq[32769], fact[10000005], ifact[10000005], f[10000005], g[10000005], ans;
int n, q;
mint get3(long long p) { return p %= MOD - 1, pw3[p & 32767] * pW3[p >> 15]; }
mint getq(long long p) { return p %= MOD - 1, pwq[p & 32767] * pWq[p >> 15]; }
mint down(int n, int m) { return fact[m] * getq((n * 2ll - m - 1) * m / 2); }
mint C(int n, int m) { return 0 <= m && m <= n ? fact[n] * ifact[n - m] * ifact[m] : 0; }
void init()
{
pw3[0] = 1;
for (int i = 1; i <= 32768; ++i)
pw3[i] = pw3[i - 1] * 3;
pW3[0] = 1;
for (int i = 1; i <= 32768; ++i)
pW3[i] = pW3[i - 1] * pw3[32768];
pwq[0] = 1;
for (int i = 1; i <= 32768; ++i)
pwq[i] = pwq[i - 1] * q;
pWq[0] = 1;
for (int i = 1; i <= 32768; ++i)
pWq[i] = pWq[i - 1] * pwq[32768];
fact[0] = 1;
for (int i = 1; i <= n; ++i)
fact[i] = fact[i - 1] * (getq(i) - 1);
ifact[n] = fact[n].inv();
for (int i = n; i; --i)
ifact[i - 1] = ifact[i] * (getq(i) - 1);
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin >> n >> q >> MOD;
init();
g[0] = 1;
for (int i = 1; i <= n; ++i)
g[i] = -getq(i - 1) * g[i - 1] * ifact[i] * fact[i - 1];
f[0] = g[0];
for (int i = 1; i <= n; ++i)
f[i] = ((getq(n) - getq(i - 1)) * f[i - 1] + g[i]) * getq(MOD - 1 - i);
int t = 1;
for (int i = 1; i <= n; ++i)
t = 1ll * t * q % (MOD - 1);
for (int i = 0, j = 1; i <= n; ++i, j = 1ll * j * t % (MOD - 1))
ans += get3(j) * f[n - i] * fact[n] * ifact[i];
std::cout << ans << std::endl;
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 9ms
memory: 160204kb
input:
1 2 540053233
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 4ms
memory: 160100kb
input:
2 2 156542707
output:
43046970
result:
ok 1 number(s): "43046970"
Test #3:
score: 0
Accepted
time: 11ms
memory: 160200kb
input:
1 2 186225229
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 10ms
memory: 160100kb
input:
3 3 109884329
output:
100602209
result:
ok 1 number(s): "100602209"
Test #5:
score: 0
Accepted
time: 12ms
memory: 160156kb
input:
1 2 144802297
output:
9
result:
ok 1 number(s): "9"
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 20
Accepted
time: 12ms
memory: 160164kb
input:
20 21992843 328859143
output:
110137213
result:
ok 1 number(s): "110137213"
Test #7:
score: 0
Accepted
time: 9ms
memory: 160200kb
input:
22 332524739 654888401
output:
410922781
result:
ok 1 number(s): "410922781"
Test #8:
score: 0
Accepted
time: 4ms
memory: 160092kb
input:
26 302215049 566649113
output:
221720840
result:
ok 1 number(s): "221720840"
Test #9:
score: 0
Accepted
time: 8ms
memory: 160340kb
input:
15 111009527 722130737
output:
648834664
result:
ok 1 number(s): "648834664"
Test #10:
score: 0
Accepted
time: 4ms
memory: 160096kb
input:
82 110032063 394529383
output:
111730592
result:
ok 1 number(s): "111730592"
Test #11:
score: 0
Accepted
time: 6ms
memory: 160152kb
input:
9 11172911 259650437
output:
68381774
result:
ok 1 number(s): "68381774"
Test #12:
score: 0
Accepted
time: 10ms
memory: 160112kb
input:
86 12016027 354886243
output:
263687778
result:
ok 1 number(s): "263687778"
Test #13:
score: 0
Accepted
time: 10ms
memory: 160164kb
input:
91 273689959 454097881
output:
114436127
result:
ok 1 number(s): "114436127"
Test #14:
score: 0
Accepted
time: 11ms
memory: 160316kb
input:
73 148878967 694206977
output:
176215101
result:
ok 1 number(s): "176215101"
Test #15:
score: 0
Accepted
time: 5ms
memory: 160164kb
input:
45 205982233 227598247
output:
156769598
result:
ok 1 number(s): "156769598"
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #16:
score: 10
Accepted
time: 10ms
memory: 160096kb
input:
2778 122825869 147297463
output:
43419574
result:
ok 1 number(s): "43419574"
Test #17:
score: 0
Accepted
time: 14ms
memory: 160284kb
input:
289 7729669 589652893
output:
552952137
result:
ok 1 number(s): "552952137"
Test #18:
score: 0
Accepted
time: 6ms
memory: 160168kb
input:
2281 35651417 203950963
output:
21659018
result:
ok 1 number(s): "21659018"
Test #19:
score: 0
Accepted
time: 4ms
memory: 160164kb
input:
1684 258745639 373223677
output:
355596229
result:
ok 1 number(s): "355596229"
Test #20:
score: 0
Accepted
time: 16ms
memory: 160204kb
input:
2107 86850989 455823859
output:
245960059
result:
ok 1 number(s): "245960059"
Test #21:
score: 0
Accepted
time: 6ms
memory: 160288kb
input:
1323 43290799 791120419
output:
509649562
result:
ok 1 number(s): "509649562"
Test #22:
score: 0
Accepted
time: 8ms
memory: 160344kb
input:
2401 34064903 185314627
output:
70571452
result:
ok 1 number(s): "70571452"
Test #23:
score: 0
Accepted
time: 0ms
memory: 160164kb
input:
1073 82288187 564447959
output:
168200843
result:
ok 1 number(s): "168200843"
Test #24:
score: 0
Accepted
time: 6ms
memory: 160160kb
input:
1926 29995039 129122281
output:
60921463
result:
ok 1 number(s): "60921463"
Test #25:
score: 0
Accepted
time: 3ms
memory: 160156kb
input:
3000 66915659 765705179
output:
222619979
result:
ok 1 number(s): "222619979"
Subtask #4:
score: 20
Accepted
Test #26:
score: 20
Accepted
time: 206ms
memory: 160208kb
input:
998818 198334853 998244353
output:
153251445
result:
ok 1 number(s): "153251445"
Test #27:
score: 0
Accepted
time: 199ms
memory: 160160kb
input:
914379 128814383 998244353
output:
477606145
result:
ok 1 number(s): "477606145"
Test #28:
score: 0
Accepted
time: 186ms
memory: 160136kb
input:
944474 478445339 998244353
output:
174204073
result:
ok 1 number(s): "174204073"
Test #29:
score: 0
Accepted
time: 217ms
memory: 160204kb
input:
948637 711592127 998244353
output:
178256114
result:
ok 1 number(s): "178256114"
Test #30:
score: 0
Accepted
time: 200ms
memory: 160164kb
input:
927564 14465663 998244353
output:
315244613
result:
ok 1 number(s): "315244613"
Test #31:
score: 0
Accepted
time: 196ms
memory: 160200kb
input:
934615 392799073 998244353
output:
892700270
result:
ok 1 number(s): "892700270"
Test #32:
score: 0
Accepted
time: 187ms
memory: 160340kb
input:
917196 124972031 998244353
output:
782017412
result:
ok 1 number(s): "782017412"
Test #33:
score: 0
Accepted
time: 193ms
memory: 160148kb
input:
957149 392606173 998244353
output:
159348443
result:
ok 1 number(s): "159348443"
Test #34:
score: 0
Accepted
time: 204ms
memory: 160100kb
input:
997042 184649453 998244353
output:
464643024
result:
ok 1 number(s): "464643024"
Test #35:
score: 0
Accepted
time: 197ms
memory: 160164kb
input:
953353 14071961 998244353
output:
391688875
result:
ok 1 number(s): "391688875"
Subtask #5:
score: 10
Accepted
Test #36:
score: 10
Accepted
time: 1924ms
memory: 160160kb
input:
9909956 720431399 720431401
output:
86883659
result:
ok 1 number(s): "86883659"
Test #37:
score: 0
Accepted
time: 1964ms
memory: 160096kb
input:
9924163 267052829 267052831
output:
75754681
result:
ok 1 number(s): "75754681"
Test #38:
score: 0
Accepted
time: 1956ms
memory: 160156kb
input:
9967885 197873129 197873131
output:
16653739
result:
ok 1 number(s): "16653739"
Test #39:
score: 0
Accepted
time: 1929ms
memory: 160204kb
input:
9952642 101872151 101872153
output:
0
result:
ok 1 number(s): "0"
Test #40:
score: 0
Accepted
time: 1937ms
memory: 160096kb
input:
9955909 167874431 167874433
output:
130012020
result:
ok 1 number(s): "130012020"
Test #41:
score: 0
Accepted
time: 1936ms
memory: 160196kb
input:
9994785 399509567 399509569
output:
153324498
result:
ok 1 number(s): "153324498"
Test #42:
score: 0
Accepted
time: 1929ms
memory: 160344kb
input:
9954011 108819131 108819133
output:
101671540
result:
ok 1 number(s): "101671540"
Test #43:
score: 0
Accepted
time: 1942ms
memory: 160164kb
input:
9997570 213315827 213315829
output:
57441081
result:
ok 1 number(s): "57441081"
Test #44:
score: 0
Accepted
time: 1945ms
memory: 160144kb
input:
9995867 113028299 113028301
output:
67837072
result:
ok 1 number(s): "67837072"
Test #45:
score: 0
Accepted
time: 1917ms
memory: 160152kb
input:
9909335 247275617 247275619
output:
202966817
result:
ok 1 number(s): "202966817"
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #46:
score: 30
Accepted
time: 1997ms
memory: 160160kb
input:
9921815 38466881 725310841
output:
601117286
result:
ok 1 number(s): "601117286"
Test #47:
score: -30
Time Limit Exceeded
input:
9919464 4830599 747345523