QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277681#6678. Gem Island 2ucup-team191#AC ✓1280ms296428kbC++141.9kb2023-12-06 21:25:052023-12-06 21:25:07

Judging History

你现在查看的是测评时间为 2023-12-06 21:25:07 的历史记录

  • [2024-10-14 17:59:23]
  • 管理员手动重测该提交记录
  • 测评结果:AC
  • 用时:1231ms
  • 内存:299088kb
  • [2024-04-23 17:43:38]
  • hack成功,自动添加数据
  • (/hack/600)
  • [2023-12-06 21:25:07]
  • 评测
  • 测评结果:100
  • 用时:1280ms
  • 内存:296428kb
  • [2023-12-06 21:25:05]
  • 提交

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],cn1[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,cn1[d-1-n*m]);
        return s;
    }
    for (int m=0;m<d/c;++m)
    {
        //ad(s,cho(n+d-1-c*(m+1),n-1));
        ad(s,cn1[n+d-1-c*(m+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;
    for (int i=n-1;i<=n-1+d;++i) cn1[i]=cho(i,n-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;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 271ms
memory: 237820kb

input:

2 3 1

output:

499122180

result:

ok 1 number(s): "499122180"

Test #2:

score: 0
Accepted
time: 261ms
memory: 237828kb

input:

3 3 2

output:

698771052

result:

ok 1 number(s): "698771052"

Test #3:

score: 0
Accepted
time: 223ms
memory: 237776kb

input:

5 10 3

output:

176512750

result:

ok 1 number(s): "176512750"

Test #4:

score: 0
Accepted
time: 253ms
memory: 238000kb

input:

5 4 3

output:

71303175

result:

ok 1 number(s): "71303175"

Test #5:

score: 0
Accepted
time: 260ms
memory: 237820kb

input:

37 47 12

output:

962577218

result:

ok 1 number(s): "962577218"

Test #6:

score: 0
Accepted
time: 263ms
memory: 237832kb

input:

29 50 26

output:

175627840

result:

ok 1 number(s): "175627840"

Test #7:

score: 0
Accepted
time: 260ms
memory: 237824kb

input:

298 498 221

output:

765832019

result:

ok 1 number(s): "765832019"

Test #8:

score: 0
Accepted
time: 272ms
memory: 237836kb

input:

497 456 243

output:

414028615

result:

ok 1 number(s): "414028615"

Test #9:

score: 0
Accepted
time: 280ms
memory: 237836kb

input:

114514 1926 817

output:

691374994

result:

ok 1 number(s): "691374994"

Test #10:

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

input:

1919810 1554 1999

output:

3553

result:

ok 1 number(s): "3553"

Test #11:

score: 0
Accepted
time: 260ms
memory: 237784kb

input:

1926817 1514 1001

output:

685086550

result:

ok 1 number(s): "685086550"

Test #12:

score: 0
Accepted
time: 273ms
memory: 238012kb

input:

1432132 1425 1425

output:

2850

result:

ok 1 number(s): "2850"

Test #13:

score: 0
Accepted
time: 299ms
memory: 296424kb

input:

14999999 15000000 14999999

output:

29999999

result:

ok 1 number(s): "29999999"

Test #14:

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

input:

98765 99654 85647

output:

815183913

result:

ok 1 number(s): "815183913"

Test #15:

score: 0
Accepted
time: 223ms
memory: 238224kb

input:

99999 100000 99998

output:

832290200

result:

ok 1 number(s): "832290200"

Test #16:

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

input:

1541 99998 725

output:

463021366

result:

ok 1 number(s): "463021366"

Test #17:

score: 0
Accepted
time: 269ms
memory: 241844kb

input:

985438 998756 101254

output:

671487608

result:

ok 1 number(s): "671487608"

Test #18:

score: 0
Accepted
time: 313ms
memory: 241736kb

input:

998654 999856 2

output:

92085960

result:

ok 1 number(s): "92085960"

Test #19:

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

input:

45876 1000000 13

output:

208089291

result:

ok 1 number(s): "208089291"

Test #20:

score: 0
Accepted
time: 1280ms
memory: 296424kb

input:

15000000 14999999 514

output:

143843956

result:

ok 1 number(s): "143843956"

Test #21:

score: 0
Accepted
time: 568ms
memory: 296416kb

input:

14985345 14999998 145124

output:

785676527

result:

ok 1 number(s): "785676527"

Test #22:

score: 0
Accepted
time: 437ms
memory: 296400kb

input:

14855345 14993298 1451424

output:

779861797

result:

ok 1 number(s): "779861797"

Test #23:

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

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 275ms
memory: 296428kb

input:

15000000 15000000 15000000

output:

30000000

result:

ok 1 number(s): "30000000"