QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397143 | #6678. Gem Island 2 | zhouhuanyi | WA | 267ms | 240424kb | C++14 | 1.4kb | 2024-04-23 17:34:56 | 2024-04-23 17:34:57 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 30000000
#define mod 998244353
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int fast_pow(int a,int b)
{
int res=1,mul=a;
while (b)
{
if (b&1) res=1ll*res*mul%mod;
mul=1ll*mul*mul%mod,b>>=1;
}
return res;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
void Adder2(int &x,int d)
{
x+=d;
if (x<0) x+=mod;
return;
}
int n,d,r,F[N+1],G[N+1],fac[N+1],invfac[N+1],ans;
int C(int x,int y)
{
return 1ll*fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
int main()
{
int res;
fac[0]=1;
for (int i=1;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod;
invfac[N]=fast_pow(fac[N],mod-2);
for (int i=N-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
n=read(),d=read(),r=read(),F[1]=1;
for (int i=r+1;i<=n;++i)
{
if (!((i-r)&1)) F[i]=C(i-2,r-1);
else F[i]=MD2(-C(i-2,r-1));
}
for (int i=1;i<=n;++i) F[i]=1ll*F[i]*C(n,i)%mod;
for (int i=0;i<=d;++i) G[i]=C(n-1+d-i,n-1);
for (int i=1;i<=n;++i)
{
res=0;
for (int j=1;j<=min(n,d/i);++j) Adder(res,G[i*j]);
Adder(ans,1ll*F[i]*res%mod);
}
printf("%d\n",MD(1ll*ans*fast_pow(C(n-1+d,n-1),mod-2)%mod+r));
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 267ms
memory: 240424kb
input:
2 3 1
output:
3
result:
wrong answer 1st numbers differ - expected: '499122180', found: '3'