感谢乘法逆元!感谢快速幂!感谢费马小定理!(逃
参考题解:
https://www.luogu.org/blog/user29936/solution-p1641
https://www.luogu.org/blog/user35379/solution-p1641
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include<iostream> #define ll long long #define MOD 20100403 using namespace std; ll quickpow(ll a,ll b){ if(b==0)return 1; ll re=quickpow(a,b/2)%MOD; re=re*re%MOD; if(b%2!=0)re=re*a%MOD; return re%MOD; } ll inv(ll x){ return quickpow(x,MOD-2)%MOD; } ll C(ll n,ll m){ ll re=1; for(ll i=n;i>=n-m+1;i--){ re=re*i%MOD; } ll fact=1; for(ll i=1;i<=m;i++){ fact=fact*i%MOD; } ll invFact=inv(fact); return re*invFact%MOD; } int main(){ ll n,m; cin>>n>>m; cout<<(C(n+m,n)%MOD-C(n+m,n+1)%MOD+MOD)%MOD; } |