2017.9.12 claris的剑 失败总结

今天的题怎么都这么难，不是搞常数就是劲逻辑

没想到组合数学学的这么差、连插板法都没有看出来、、

首先两个两个分组（分组的思想很重要）

然后本质不同就利用上了，即选的组数量不同

然后就是枚举所有m，然后用组合数往里填，即把除去m个数之外的空间/2来放其他组

从1做到（n+m）/2的话一个组合数就搞定了

对于奇偶就只需在最后添加一个小的就可以保证不重不漏（递推可证）

然而一开始做的时候连式子都列不出来，最后离散选择变成几次方的形式，就直接错了（重复）

所以无论如何应该先把式子列出来，然后再看一看有没有可以化简的地方

注意组合数有时有很巧妙的化简套路（如前缀和直接变成一个组合数）

6个月前做过这个题，然后就怀疑人生，就再也不想碰数学了

码（借（chao）鉴（de））：

#include<iostream>  
#include<cstdio>  
#define ll long long  
using namespace std;  
#define P 1000000007   
int n,m,f[2000005],ni[2000005],i,ans;  
int C(int x,int y){  
    if (x<0) return 0; x/=2; y--;  
    return (ll)f[x+y]*ni[x]%P*ni[y]%P;  
}  
int main(){  
    scanf("%d%d",&n,&m);   
    f[0]=f[1]=ni[0]=ni[1]=1;  
    for (i=2; i<=n; i++){  
        f[i]=1ll*f[i-1]*i%P; ni[i]=1ll*ni[P%i]*(P-P/i)%P;  
    }  
    for (i=2; i<=n; i++) ni[i]=1ll*ni[i]*ni[i-1]%P;  
     if (m&&n) ans=1;
	  m=min(n,m);  
    for (i=2; i<=m; i++){  
        ans=((ans+C(n-i,i))%P+C(n-i-1,i))%P;  
    }  
    printf("%d",ans);   
}