整理题意后 对于每个询问其实就是
由于C(m,n)=C(m,m-n)
就变成了
其实就是在杨辉三角上的一列求其中的一段和
然后有个玄学的公式
什么意思呢
证明是很容易得到的
所以把阶乘预处理出来 由于1e9+7是质数 可以用费马小定理算逆元 就可以O(1)回答
#include<bits/stdc++.h> #define N 100010 #define mod 1000000007 #define int long long using namespace std; inline int qpow(int x,int y) { int base=x,ans=1; while(y) { if(y&1) ans=(ans*base)%mod; base=(base*base)%mod; y>>=1; } return ans; } int n,m,fac[N],inv[N]; void init() { fac[0]=1; for(int i=1;i<=n+5;i++) fac[i]=fac[i-1]*i%mod; for(int i=0;i<=n+5;i++) inv[i]=qpow(fac[i],mod-2); } int C(int m,int n) { return ((fac[m]*inv[n])%mod*inv[m-n])%mod; } main() { cin>>n>>m; init(); int ans=1; for(int i=1;i<=m;i++) { int l,r,k; scanf("%d%d%d",&l,&r,&k); int tmp=C(r+1,l-k+1)-C(l,l-k+1); while (tmp<0) tmp+=mod; ans=ans*tmp%mod; } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9798236.html
相关资源：各显卡算力对照表！