QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412897#6736. Alice and BobZhazAC ✓725ms159912kbC++171.8kb2024-05-16 21:22:252024-05-16 21:22:26

Judging History

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

  • [2024-05-16 21:22:26]
  • 评测
  • 测评结果:AC
  • 用时:725ms
  • 内存:159912kb
  • [2024-05-16 21:22:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl "\n"
#define PII pair<double,int>
// const int maxn=1e7+5;
// const int mod=998244353;
const int N = 1e7 + 3, mod = 998244353;
const int maxn = 25000001;
const int p = 998244353;
namespace CNM {
    const int N = 1e7 + 4;
    int fac[N], infac[N];
    int ksm(int x, int y) {
        int res = 1;
        while(y > 0) {
            if(y & 1)
                res = res * x % p;
            y >>= 1;
            x = x * x % p;
        }
        return res;
    }
    void init() {
        fac[0] = 1;
        for(int i = 1; i < N; i ++)
            fac[i] = fac[i - 1] * i % p;
        infac[N - 1] = ksm(fac[N - 1], p - 2);
        for(int i = N - 2; i >= 0; i --)
            infac[i] = infac[i + 1] * (i + 1) % p;
    }
    int C(int n, int m) {
        if(n < m || m < 0) return 0;
        return (fac[n] * infac[m] % p) * infac[n - m] % p;
    }
    int A(int n, int m) {
        if(n < m || m < 0) return 0;
        return fac[n] * infac[n - m] % mod;
    }
    int inv(int x,int p){
        return ksm(x,p-2)%p;
    }
}
// int A(int n, int m) {
//     return CNM::A(n, m);
// }
int C(int n,int m){
    return CNM::C(n,m);
}
int inv(int a,int b){
    return CNM::inv(a,b);
}
signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    CNM::init();
    int n;cin>>n;
    int ans=CNM::fac[n-1];
    
    int s=1,x=n-2;
    for(int i=2;i<=n;i++){
        int temp=C(x,s)*CNM::fac[n-1]%p;
        ans+=temp*inv(C(n-1,i-1),p)%mod;
        ans%=p;
        // printf("%d %d %d\n",i,temp,inv(C(n-1,i-1),p));
        x--;s++;
        if(s>x)break;
    }
    if(n==1)ans=1;
    cout<<ans<<endl;


    
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 79ms
memory: 159740kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 84ms
memory: 159664kb

input:

2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 83ms
memory: 159664kb

input:

10

output:

997920

result:

ok 1 number(s): "997920"

Test #4:

score: 0
Accepted
time: 78ms
memory: 159700kb

input:

100

output:

188898954

result:

ok 1 number(s): "188898954"

Test #5:

score: 0
Accepted
time: 85ms
memory: 159772kb

input:

4

output:

10

result:

ok 1 number(s): "10"

Test #6:

score: 0
Accepted
time: 85ms
memory: 159744kb

input:

8

output:

12336

result:

ok 1 number(s): "12336"

Test #7:

score: 0
Accepted
time: 81ms
memory: 159744kb

input:

16

output:

373118483

result:

ok 1 number(s): "373118483"

Test #8:

score: 0
Accepted
time: 79ms
memory: 159908kb

input:

32

output:

314585464

result:

ok 1 number(s): "314585464"

Test #9:

score: 0
Accepted
time: 87ms
memory: 159912kb

input:

64

output:

627827331

result:

ok 1 number(s): "627827331"

Test #10:

score: 0
Accepted
time: 87ms
memory: 159844kb

input:

128

output:

828497685

result:

ok 1 number(s): "828497685"

Test #11:

score: 0
Accepted
time: 82ms
memory: 159840kb

input:

256

output:

65697890

result:

ok 1 number(s): "65697890"

Test #12:

score: 0
Accepted
time: 78ms
memory: 159848kb

input:

512

output:

854187619

result:

ok 1 number(s): "854187619"

Test #13:

score: 0
Accepted
time: 87ms
memory: 159736kb

input:

1024

output:

513823539

result:

ok 1 number(s): "513823539"

Test #14:

score: 0
Accepted
time: 172ms
memory: 159660kb

input:

1361956

output:

617368199

result:

ok 1 number(s): "617368199"

Test #15:

score: 0
Accepted
time: 562ms
memory: 159744kb

input:

7579013

output:

827172636

result:

ok 1 number(s): "827172636"

Test #16:

score: 0
Accepted
time: 597ms
memory: 159740kb

input:

8145517

output:

710624331

result:

ok 1 number(s): "710624331"

Test #17:

score: 0
Accepted
time: 468ms
memory: 159672kb

input:

6140463

output:

707600568

result:

ok 1 number(s): "707600568"

Test #18:

score: 0
Accepted
time: 309ms
memory: 159748kb

input:

3515281

output:

698302413

result:

ok 1 number(s): "698302413"

Test #19:

score: 0
Accepted
time: 528ms
memory: 159760kb

input:

6969586

output:

69470392

result:

ok 1 number(s): "69470392"

Test #20:

score: 0
Accepted
time: 264ms
memory: 159744kb

input:

2888636

output:

433579983

result:

ok 1 number(s): "433579983"

Test #21:

score: 0
Accepted
time: 725ms
memory: 159820kb

input:

9999998

output:

758172780

result:

ok 1 number(s): "758172780"

Test #22:

score: 0
Accepted
time: 705ms
memory: 159744kb

input:

9999999

output:

605195495

result:

ok 1 number(s): "605195495"

Test #23:

score: 0
Accepted
time: 704ms
memory: 159908kb

input:

10000000

output:

866813682

result:

ok 1 number(s): "866813682"