【2018/10/16测试T1】膜法

【题目】

内网传送门
外网传送门

【分析】

做这道题之前，先储备一些关于组合数的知识吧
$C_n^m=C_n^{n-m}$Cnm​=Cnn−m​
$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$Cn0​+Cn1​+Cn2​+...+Cnn​=2n
注：这些公式可能对下面的题解无关，但对自己推公式的话应该是有一定帮助的

30 pts：

根据乘法原理，最后的答案为每个环节的方案数乘起来。

根据加法原理，每个环节的方案书为 $\sum_{j=l}^{\;\;r} \;C_{\;\;\;\;\;j}^{k_i+j-l}$∑j=lr​Cjki​+j−l​。

可以直接预处理出组合数，然后 O（$nm$nm）暴力枚举求解即可。

60 pts：

容易发现我们加的是组合数表中一个斜线上的所有组合数。

O$(n^2)$(n2) 预处理组合数及其斜线上的前缀和，然后 O$(m)$(m) 统计。

100 pts：

注意到以下公式的转换：

$\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​

因此我们只需求两个组合数即可，预处理出阶乘和阶乘的逆元即可

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#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;
}