1 条题解
-
3
思路
根据题目提示: $\\C_n^m=\frac{n*(n-1)* \cdots *(n-m+1)}{m!}=\frac{n!}{m!*(n-m)!}$。 $\\$我们需要求出$n!$模$998244353$的结果和$n!$关于$998244353$的逆元. $\\$定义f[i]，表示$i!$模998244353结果，直接递推求出。 $\\$定义inv[i]，表示$i$关于$998244353$的逆元,这一部分根据课上的公式：$inv[i]=(mod-k)*inv[r]%mod;$可以求出。 $\\$定义finv[i]，表示$i!$关于$998244353$的逆元，可以利用$inv[i]$递推求出。 $\\$最后：$\\C_n^m=f[i]*finv[n-m]*finv[m]$。代码
#include<bits/stdc++.h> using namespace std; const long long mod=998244353; const long long N=5000005; long long n,m; long long f[N],inv[N],finv[N]; int main( ) { cin >>n>>m; f[1]=1; for(int i=2;i<=n;i++) f[i]=f[i-1]*i%mod; inv[1]=1; finv[1]=1; for(int i=2;i<=n;i++) { long long k=mod/i,r=mod%i; inv[i]=(mod-k)*inv[r]%mod; finv[i]=finv[i-1]*inv[i]%mod; } cout<<f[n]*finv[n-m]%mod*finv[m]%mod; return 0; }
- 1