QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#200739 | #6678. Gem Island 2 | lmeowdn | AC ✓ | 1450ms | 945200kb | C++14 | 2.2kb | 2023-10-04 19:15:09 | 2024-04-23 17:46:56 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=3e7+5,mod=998244353;
int n,d,r,m,fac[N],inv[N],ifac[N],f[N],ans;
bitset<N> vst;
int ksm(int x,int y,int res=1) {
for(;y;y>>=1,x=x*x%mod) if(y%2==1) res=res*x%mod;
return res;
}
void pre(int n) {
inv[0]=inv[1]=fac[0]=ifac[0]=1;
rep(i,1,n) fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n],mod-2);
per(i,n-1,1) ifac[i]=ifac[i+1]*(i+1)%mod;
rep(i,2,n) inv[i]=ifac[i]*fac[i-1]%mod;
}
int C(int x,int y) {
if(x<0||y<0||x<y) return 0;
else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
signed main() {
n=read(), d=read(), r=read(), m=n+d;
pre(m); int p=C(n+d-1,n-1);
rep(i,1,m) f[i]=C(n+d-i-1,n-1);
rep(i,2,m) if(!vst[i]) {
per(j,m/i,1)
vst[i*j]=1, f[j]=(f[j]+f[i*j])%mod;
}
ans=f[1]*n%mod;
rep(i,r+1,n) {
int res=f[i]*C(n,i)%mod*C(i-2,r-1)%mod;
if((i+r)&1) ans=(ans+mod-res)%mod;
else ans=(ans+res)%mod;
}
printf("%lld\n",(ans*ksm(p,mod-2)+r)%mod);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 12200kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: 0
Accepted
time: 2ms
memory: 12016kb
input:
3 3 2
output:
698771052
result:
ok 1 number(s): "698771052"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11896kb
input:
5 10 3
output:
176512750
result:
ok 1 number(s): "176512750"
Test #4:
score: 0
Accepted
time: 1ms
memory: 11888kb
input:
5 4 3
output:
71303175
result:
ok 1 number(s): "71303175"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11936kb
input:
37 47 12
output:
962577218
result:
ok 1 number(s): "962577218"
Test #6:
score: 0
Accepted
time: 2ms
memory: 11948kb
input:
29 50 26
output:
175627840
result:
ok 1 number(s): "175627840"
Test #7:
score: 0
Accepted
time: 0ms
memory: 11992kb
input:
298 498 221
output:
765832019
result:
ok 1 number(s): "765832019"
Test #8:
score: 0
Accepted
time: 0ms
memory: 12200kb
input:
497 456 243
output:
414028615
result:
ok 1 number(s): "414028615"
Test #9:
score: 0
Accepted
time: 0ms
memory: 14284kb
input:
114514 1926 817
output:
691374994
result:
ok 1 number(s): "691374994"
Test #10:
score: 0
Accepted
time: 59ms
memory: 71596kb
input:
1919810 1554 1999
output:
3553
result:
ok 1 number(s): "3553"
Test #11:
score: 0
Accepted
time: 62ms
memory: 73672kb
input:
1926817 1514 1001
output:
685086550
result:
ok 1 number(s): "685086550"
Test #12:
score: 0
Accepted
time: 41ms
memory: 57164kb
input:
1432132 1425 1425
output:
2850
result:
ok 1 number(s): "2850"
Test #13:
score: 0
Accepted
time: 1311ms
memory: 945200kb
input:
14999999 15000000 14999999
output:
29999999
result:
ok 1 number(s): "29999999"
Test #14:
score: 0
Accepted
time: 0ms
memory: 18164kb
input:
98765 99654 85647
output:
815183913
result:
ok 1 number(s): "815183913"
Test #15:
score: 0
Accepted
time: 7ms
memory: 18152kb
input:
99999 100000 99998
output:
832290200
result:
ok 1 number(s): "832290200"
Test #16:
score: 0
Accepted
time: 4ms
memory: 14032kb
input:
1541 99998 725
output:
463021366
result:
ok 1 number(s): "463021366"
Test #17:
score: 0
Accepted
time: 56ms
memory: 73564kb
input:
985438 998756 101254
output:
671487608
result:
ok 1 number(s): "671487608"
Test #18:
score: 0
Accepted
time: 46ms
memory: 75560kb
input:
998654 999856 2
output:
92085960
result:
ok 1 number(s): "92085960"
Test #19:
score: 0
Accepted
time: 23ms
memory: 44904kb
input:
45876 1000000 13
output:
208089291
result:
ok 1 number(s): "208089291"
Test #20:
score: 0
Accepted
time: 1450ms
memory: 944904kb
input:
15000000 14999999 514
output:
143843956
result:
ok 1 number(s): "143843956"
Test #21:
score: 0
Accepted
time: 1411ms
memory: 944800kb
input:
14985345 14999998 145124
output:
785676527
result:
ok 1 number(s): "785676527"
Test #22:
score: 0
Accepted
time: 1412ms
memory: 945080kb
input:
14855345 14993298 1451424
output:
779861797
result:
ok 1 number(s): "779861797"
Test #23:
score: 0
Accepted
time: 0ms
memory: 11940kb
input:
1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 1275ms
memory: 944908kb
input:
15000000 15000000 15000000
output:
30000000
result:
ok 1 number(s): "30000000"
Extra Test:
score: 0
Extra Test Passed