奇怪
查看原帖
奇怪
315205
Kniqht楼主2022/10/7 16:50

为什么我推出来的公式是 C(i,n-1)-C(i,n-2) (1<=i<=n且i*2!=n)的和呢,但是题解区似乎跟我都不一样,但是我得了80分

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,mod=998244353;
int n,m;
ll fact[N],infact[N],ans;
ll qpow(ll x){
    ll res=1,p=mod-2;
    while(p){
        if(p&1) res=(res*x)%mod;
        x=(x*x)%mod;p>>=1;
    }
    return res;
}
ll get_c(ll x,ll y){return fact[x]*infact[y]%mod*infact[x-y]%mod;}
int main(){
    scanf("%d",&n);
    if(n==1){printf("0");return 0;}
    fact[0]=infact[0]=1;
    for(ll i=1;i<=n;i++){
        fact[i]=(fact[i-1]*i)%mod;
        infact[i]=(infact[i-1]*qpow(i))%mod;
    }
    for(int i=1;i<=n;i++){
        if(i*2==n) continue;
        ans=(ans+get_c(n-1,i)-get_c(n-2,i))%mod;
    }
    printf("%lld",ans);
    return 0;
}

2022/10/7 16:50
加载中...