bzoj 4402 Claris的剑组合数学

Claris的剑

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 375 Solved: 213
[Submit][Status][Discuss]

Description

Claris想要铸一把剑，这把剑必须符合他的审美，具体来说，我们可以把这把剑的不同地方的宽度看成一个序列，这个序列要满足以下条件：
1.每个元素都是正整数（你的宽度不可能是负数吧）
2.每个元素不能超过M，太宽了如果比Claris身高还高怎么办（你可以认为Claris的身高就是M）
3.相邻两个元素的差的绝对值必须是1（如果是0，则这个地方不是锯齿，杀伤力不够，如果太大，又太丑了）
4.第一个元素的值必须是1（剑尖必须是最窄的地方）
他想知道有多少把长度不超过N（即宽度的序列长度不超过N）的合法的本质不同的剑。
我们认为两把剑本质不同，当且仅当存在至少一个宽度，在两把剑的宽度序列里面出现次数不一样。
比如{1,2,3}和{1,3,2}是本质相同的
{1,2,3}和{1,2,1}则是本质不同的

Input

只有两个整数，表示N,M (数据保证$N,M leq 2000000$)

Output

只有一个整数，表示答案对$10^9+7$取模的结果

Sample Input

5 3

Sample Output

HINT

样例解释

所有本质不同的合法的剑有如下：

{1}

{1,2}

{1,2,3}

{1,2,1}

{1,2,3,2}

{1,2,1,2}

{1,2,3,2,3}

{1,2,3,2,1}

{1,2,1,2,1}

 1 #include<cstring>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cstdio>
 6 #include<queue>
 7 
 8 #define mod 1000000007
 9 #define N 2000007
10 using namespace std;
11 inline int read()
12 {
13     int x=0,f=1;char ch=getchar();
14     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
15     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 
19 int n,m,Lim;
20 long long ans,mul[N],inv[N];
21 
22 long long C(int n,int m)
23 {
24     if (n<m) return 0;
25     long long tmp=mul[n];
26     tmp=tmp*inv[m]%mod;
27     tmp=tmp*inv[n-m]%mod;
28     return tmp;
29 }
30 int main()
31 {
32     n=read(),m=read();
33     if (m==0){printf("0
");return 0;}
34     Lim=max(n,m)+10;
35     mul[0]=1;inv[1]=1;inv[0]=1;
36     for (int i=1;i<=Lim;i++) mul[i]=mul[i-1]*i%mod;
37     for (int i=2;i<=Lim;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
38     for (int i=1;i<=Lim;i++) inv[i]=inv[i]*inv[i-1]%mod;
39     Lim=min(m-2,n-2);
40     for (int i=0;i<=Lim;i++)
41     {
42         int lim=(n-i)/2,Max;
43         Max=i+lim-1;
44         ans=(ans+C(Max+1,i+1)*2)%mod;
45         if ((n-i)%2==0) ans=(ans-C(Max,i))%mod;
46     }
47     ans=(ans-(Lim+1)+min(n,m))%mod;
48     ans=(ans+mod)%mod;
49     printf("%lld
",ans);
50 }