【推式子二项式定理】Wannafly挑战赛 B

向右看齐 2024-03-17 13:43 54阅读 0赞

[B-求值2\_Wannafly挑战赛17 (nowcoder.com)][B-_2_Wannafly_17 _nowcoder.com]

题意：

![c474854b14ef44a3934dbed21aad7373.png][]

![9504c043cab94588b33e45395366a069.png][]

思路：

![107a5d0a1cef420cab34e7fbd5ec237a.jpeg][]

![a4541b71df8f4526a8bdc73131976138.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e6+10;
    const int mxe=2e5+10;
    const int Inf=0x3f3f3f3f;
    const int mod=998244353;
    
    int N;
    int Fac[mxn],inv[mxn];
    
    int ksm(int a,int b,int mod){
    	int res=1;
    	while(b){
    		if(b&1) res=(res*a)%mod;
    		a=(a*a)%mod;
    		b>>=1;
    	}
    	return res;
    }
    void F_init(){
    	Fac[1]=1;
    	for(int i=2;i<mxn;i++) Fac[i]=(Fac[i-1]*i)%mod;
    	inv[mxn-1]=ksm(Fac[mxn-1],mod-2,mod);
    	for(int i=mxn-2;i>=1;i--) inv[i]=(inv[i+1]*(i+1))%mod;
    }
    int C(int n,int m){
    	return Fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    void solve(){
        cin>>N;
        int ans=0;
        for(int i=1;i<=N;i++){
            ans+=C(2*i,i);
            ans%=mod;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
    	F_init();
        while(__--)solve();return 0;
    }

[B-_2_Wannafly_17 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/114/B
[c474854b14ef44a3934dbed21aad7373.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a4b77e3322f44230a9265d7e3392d141.png
[9504c043cab94588b33e45395366a069.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e8cbdc5c59494cbc87715fe98b4ba98f.png
[107a5d0a1cef420cab34e7fbd5ec237a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d2524a1609b3446aa4ad126299694964.png
[a4541b71df8f4526a8bdc73131976138.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b7d10ed8c819446dae678a6b3b384c48.png