题目大意
给定若干组询问求$\sum\limits_{i=l}^r \dbinom{i}{k}$。
最终输出每组询问答案的乘积。
题解
首先把$l,r$分开处理相减，只需要求$\sum\limits_{i=1}^r \dbinom{i}{k}$即可
解法一：打表找规律
你会轻而易举的发现$\sum\limits_{i=1}^r \dbinom{i}{k}=\dbinom{r+1}{k+1}$
解法二：组合数意义
$\sum$在$1....n$个位置放$K$个的方案数$=$在$n+1$个位置安排$K+1$个并枚举最后一个放在哪里$=\dbinom{n+1}{k+1}$
解法三：整数裂项
$$\frac{\sum i(i-1)...(i-k+1)}{k!}$$
$$\sum i(i-1)...(i-k+1)=\frac{\sum (i+1-(i-k))i(i-1)...(i-k+1)}{k+1}$$
展开之后不难发现$(i+1-(i-k))i(i-1)...(i-k+1)$可以两两相消，最终答案变成$$\frac{(n+1)n...(n-k+1)}{(k+1)!}=\dbinom{n+1}{k+1}$$
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<" "
#define el <<endl
#define LL long long
#define M 100020
#define mod 1000000007
using namespace std;
namespace IO{const int BS=(1<<20)+5; char Buffer[BS],*HD,*TL;char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}int read(){int nm=0,fh=1; char cw=Getchar();for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh;for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0');return nm*fh;}
}
using namespace IO;
int n,m,fac[M],inv[M];LL ans;
LL F(int tot,int tk){if(tot<tk)return 0;return ((LL)fac[tot]*(LL)inv[tk]%mod)*(LL)inv[tot-tk]%mod;}
int main(){n=read(),m=read(),ans=1,fac[0]=fac[1]=inv[0]=inv[1]=1;for(int i=2;i<=n+1;i++) fac[i]=(LL)fac[i-1]*(LL)i%mod,inv[i]=(LL)(mod-(mod/i))*(LL)inv[mod%i]%mod;for(int i=2;i<=n+1;i++) inv[i]=(LL)inv[i-1]*(LL)inv[i]%mod;for(int i=1;i<=m;i++){int l=read(),r=read(),K=read();K=l-K;ans*=(F(r+1,K+1)-F(l,K+1)+mod),ans%=mod;}printf("%lld\n",ans);
}
