【テーマ】

イントラネットゲートウェイ

【分析】

この問題をする前に、まず組み合わせ数についての知識を蓄えましょう.n^m=C_n^{n-m} Cnm​=Cnn−m​ C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} Cnm​=Cn−1m​+Cn−1m−1​ C n 0 + C n 1 + C n 2 + . . . + C n n = 2 n C_n^0+C_n^1+C_n^2+...+C_n^n=2^n Cn0​+Cn1​+Cn2​+...+Cnn=2 n注:これらの式は次の問題解には関係ないかもしれませんが、自分で式を押すのに役立つはずです.
30 pts:
乗算の原理に基づいて,最後の答えは各段階のスキーム数に乗算される.
加算の原理によって、各段階の方案書はΣj=l&ThickSpaceである.ThickSpace; r    C            j k i + j − l\sum_{j=l}^{\;\;r}\;C_{\;\;\;\;\;j}^{k_i+j-l} ∑j=lr​Cjki​+j−l​.
組合せ数を直接前処理し,次いでO(nmnm)暴力列挙で解くことができる.
60 pts:
コンビネーションテーブルの斜線上のすべてのコンビネーション数を加えたことがわかりやすい.
O(n 2)(n^2)(n 2)の前処理組合せ数とその斜線上の接頭辞和を,O(m)(m)(m)統計した.
100 pts:
次の数式の変換に注意してください.
∑ j = l r C            j k i + j − l = ∑ j = l r C      j l − k i = C        r + 1 l − k i + 1 − C            l l − k i + 1\sum_{j=l}^{r}C_{\;\;\;\;\;j}^{k_i+j-l}=\sum_{j=l}^{r}C_{\;\;j}^{l-k_i}=C_{\;\;\;r+1}^{l-k_i+1}-C_{\;\;\;\;\;l}^{l-k_i+1} j=l∑r​Cjki​+j−l​=j=l∑r​Cjl−ki​​=Cr+1l−ki​+1​−Cll−ki​+1​
したがって,2つの組合せ数だけが必要であり,階乗と階乗の逆元を前処理すればよい.

【コード】

#include
#include
#include
#define N 100005
#define Mod 1000000007
using namespace std;
int fac[N],inv[N];
int dec(int x,int y)  {return (x-y+Mod)%Mod;}
int mul(int x,int y)  {return 1ll*x*y%Mod;}
int C(int n,int m)  {return mul(fac[n],mul(inv[m],inv[n-m]));}
int Power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
		  ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}
int main()
{
//	freopen("m.in","r",stdin);
//	freopen("m.out","w",stdout);
	int n,m,i,j,l,r,k,ans=1;
	scanf("%d%d",&n,&m);
	fac[0]=fac[1]=1;
	for(i=2;i<=n+1;++i)  fac[i]=mul(fac[i-1],i);
	inv[n+1]=Power(fac[n+1],Mod-2);
	for(i=n;i>=0;--i)  inv[i]=mul(inv[i+1],i+1);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&l,&r,&k);
		ans=mul(ans,dec(C(r+1,l-k+1),C(l,l-k+1)));
	}
	printf("%d",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}