QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277661#6678. Gem Island 2ucup-team191#TL 325ms238096kbC++141.8kb2023-12-06 21:16:592023-12-06 21:17:00

Judging History

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

  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-12-06 21:17:00]
  • 评测
  • 测评结果:TL
  • 用时:325ms
  • 内存:238096kb
  • [2023-12-06 21:16:59]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=30000010,MOD=998244353;
const char en='\n';
const ll LLINF=1ll<<60;

int mul(int a,int b)
{
    return a*1ll*b%MOD;
}

int pot(int n,int k)
{
    if (k==0) return 1;
    int r=pot(n,k/2);
    r=mul(r,r);
    if (k%2) r=mul(r,n);
    return r;
}

int add(int a,int b)
{
    if (a+b>=MOD) return a+b-MOD;
    return a+b;
}

void ad(int&a,int b)
{
    a+=b;
    if (a>=MOD) a-=MOD;
}

void su(int&a,int b)
{
    a-=b;
    if (a<0) a+=MOD;
}

int n,d,r,fac[N],inf[N];

int cho(int a,int b)
{
    if (b<0 || b>a) return 0;
    return mul(fac[a],mul(inf[b],inf[a-b]));
}

int RR(int b,int c,int d)
{
    return cho(c+1,b+d+1);
}

int R(int a,int b,int c,int d)
{
    return RR(b,c-a,d);
}

int F(int c)
{
    int s=0;
    if (c==n)
    {
        for (int m=0;m<=d/n;++m) ad(s,cho(d-1-n*m,n-1));
        return s;
    }
    for (int m=0;m<=d/c;++m)
    {
        ad(s,R(c*m+1,c-1,n+d-c-1,n-c-1));
    }
    return s;
}

int invcho(int a,int b)
{
    if (b<0 || b>a) return 0;
    return mul(inf[a],mul(fac[b],fac[a-b]));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    fac[0]=1;
    for (int i=1;i<N;++i) fac[i]=mul(fac[i-1],i);
    inf[N-1]=pot(fac[N-1],MOD-2);
    for (int i=N-2;i>=0;--i) inf[i]=mul(i+1,inf[i+1]);
    cin>>n>>d>>r;
    //n=1.5e7;
    //d=1.5e7;
    //r=1;
    int od=0;
    ad(od,mul(n,F(1)));
    for (int i=1;i<=n-r;++i)
    {
        if (i%2) su(od,mul(mul(cho(n,r+i),cho(i+r-2,r-1)),F(r+i)));
        else ad(od,mul(mul(cho(n,r+i),cho(i+r-2,r-1)),F(r+i)));
    }
    cout<<add(mul(od,invcho(n+d-1,n-1)),r)<<en;
}

詳細信息

Test #1:

score: 100
Accepted
time: 247ms
memory: 237964kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 250ms
memory: 238008kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 246ms
memory: 237964kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 241ms
memory: 237960kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 250ms
memory: 238020kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 242ms
memory: 238096kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 246ms
memory: 238044kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 239ms
memory: 238020kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 244ms
memory: 238008kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

score: 0
Accepted
time: 276ms
memory: 237956kb

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 265ms
memory: 237948kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 254ms
memory: 237960kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 283ms
memory: 238044kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

score: 0
Accepted
time: 238ms
memory: 238032kb

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 249ms
memory: 238092kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

score: 0
Accepted
time: 250ms
memory: 238092kb

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 268ms
memory: 237964kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 325ms
memory: 238040kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

score: 0
Accepted
time: 307ms
memory: 237964kb

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: -100
Time Limit Exceeded

input:

15000000 14999999 514

output:


result: