QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411634 | #6678. Gem Island 2 | le0n# | AC ✓ | 800ms | 378452kb | C++14 | 1.6kb | 2024-05-15 16:56:25 | 2024-05-15 16:56:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353, N = 3e7 + 5;
int fac[N], inv[N], f[N], g[N];
int prime[N], cnt;
bool ntp[N];
int qpow(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1)
ans = (ll)ans * x % mod;
x = (ll)x * x % mod;
y >>= 1;
}
return ans;
}
void prep(int n)
{
int i;
fac[0] = 1;
for(i = 1; i <= n; i++)
fac[i] = (ll)fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2);
for(i = n; i >= 1; i--)
inv[i - 1] = (ll)inv[i] * i % mod;
}
int C(int x, int y)
{
return (x < y || y < 0) ? 0 : ((ll)fac[x] * inv[y] % mod * inv[x - y] % mod);
}
void sieve(int n)
{
int i, j;
for(i = 2; i <= n; i++)
{
if(!ntp[i])
prime[++cnt] = i;
for(j = 1; j <= cnt && i * prime[j] <= n; j++)
{
ntp[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
}
void work(int n)
{
int i, j;
for(i = 1; i <= cnt; i++)
for(j = n / prime[i]; j >= 1; j--)
f[j] = (f[j] + f[j * prime[i]]) % mod;
}
int main()
{
int n, d, r, i, j, ans = 0, tmp;
prep(3e7);
sieve(1.5e7);
scanf("%d%d%d", &n, &d, &r);
for(i = 1; i <= n; i++)
{
g[i] = ((ll)i * C(i - 2, r - 2) + mod - (ll)r * C(i - 1, r - 1) % mod) % mod;
if((i + r - 1) & 1)
g[i] = mod - g[i];
}
g[1] = 1;
for(i = 1; i <= d; i++)
f[i] = C(d - i + n - 1, n - 1);
work(d);
for(i = 1; i <= n; i++)
{
tmp = (C(d + n - 1, n - 1) + f[i]) % mod;
ans = (ans + (ll)C(n, i) * tmp % mod * g[i]) % mod;
}
ans = (ll)ans * qpow(C(d + n - 1, n - 1), mod - 2) % mod;
printf("%d\n", ans);
return 0;
}
/*
15000000 15000000 1031
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 318ms
memory: 256808kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 332ms
memory: 256620kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 298ms
memory: 256740kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 298ms
memory: 262664kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 301ms
memory: 256764kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 308ms
memory: 256696kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 308ms
memory: 266432kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 296ms
memory: 256764kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 317ms
memory: 257208kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 337ms
memory: 265024kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 332ms
memory: 265224kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 327ms
memory: 262492kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 709ms
memory: 374080kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 293ms
memory: 259488kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 297ms
memory: 259240kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 293ms
memory: 259860kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 336ms
memory: 266220kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 342ms
memory: 269024kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 311ms
memory: 265612kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 785ms
memory: 376336kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 800ms
memory: 378348kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 754ms
memory: 375812kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 295ms
memory: 262504kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 701ms
memory: 378452kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed