QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200739#6678. Gem Island 2lmeowdnAC ✓1450ms945200kbC++142.2kb2023-10-04 19:15:092024-04-23 17:46:56

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 17:46:56]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1450ms
  • 内存:945200kb
  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-10-04 19:15:11]
  • 评测
  • 测评结果:100
  • 用时:1296ms
  • 内存:944952kb
  • [2023-10-04 19:15:09]
  • 提交

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