QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198959 | #6678. Gem Island 2 | jeffqi | AC ✓ | 849ms | 597520kb | C++20 | 2.0kb | 2023-10-03 19:38:41 | 2024-04-23 17:46:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;
namespace qiqi {
const int N = 3e7,P = 998244353;
array<ll,N+1> fac,ifac; vi p;
ll pow(ll b,ll k) {
ll a = 1;
for (; k; b = b*b%P,k >>= 1) {
if (k&1) {
a = a*b%P;
}
}
return a;
}
void init(int n = N) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = i*fac[i-1]%P;
}
ifac[n] = pow(fac[n],P-2);
for (int i = n; i >= 1; i--) {
ifac[i-1] = i*ifac[i]%P;
}
vi isp(n+1,1);
for (int i = 2; i <= n; i++) {
if (isp[i]) {
p.eb(i);
}
for (auto x:p|views::take_while([&](int k) {return i*k <= n;})) {
isp[i*x] = 0; if (!(i%x)) {break;}
}
}
}
ll C(int n,int m) {
return m < 0 || n < m ? 0 : fac[n]*ifac[m]%P*ifac[n-m]%P;
}
void main() {
init();
int n,d,r;
cin >> n >> d >> r;
const int m = n-1+d;
vi f(d+1); iota(f.begin(),f.end(),0);
ranges::transform(f,f.begin(),[&](int x) {
return C(m-x,n-1);
});
for (auto x:p) {
for (int i = d/x; i >= 1; i--) {
f[i] = (f[i]+f[i*x])%P;
}
}
for (int i = 1; i <= d; i++) {
f[i] = f[i]*C(n,i)%P;
}
int ans = 0;
for (int i = 1; i <= min(n,d); i++) {
ll k = f[i];
if (i != 1) {
k = k*C(i-2,r-1)%P;
if ((i+r)%2) {
k = -k;
}
}
ans = (ans+k)%P;
}
ans = (ans*pow(C(m,n-1),P-2)+r)%P;
cout << (ans+P)%P << '\n';
}
}
int main() {
// clock_t st = clock();
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
qiqi::main();
}
// cout << (double)(clock()-st)/CLOCKS_PER_SEC;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 452ms
memory: 597512kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 411ms
memory: 597316kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 369ms
memory: 597316kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 399ms
memory: 597424kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 384ms
memory: 597444kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 381ms
memory: 597472kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 405ms
memory: 597520kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 401ms
memory: 597248kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 386ms
memory: 597244kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 434ms
memory: 597460kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 396ms
memory: 597424kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 383ms
memory: 597424kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 780ms
memory: 597292kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 374ms
memory: 597296kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 435ms
memory: 597512kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 384ms
memory: 597512kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 408ms
memory: 597468kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 419ms
memory: 597320kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 401ms
memory: 597392kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 823ms
memory: 597280kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 829ms
memory: 597444kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 849ms
memory: 597424kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 416ms
memory: 597400kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 781ms
memory: 597508kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed