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

9

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}

bzoj 4402 Claris的剑 组合数学-LMLPHP

 #include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue> #define mod 1000000007
#define N 2000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,Lim;
long long ans,mul[N],inv[N]; long long C(int n,int m)
{
if (n<m) return ;
long long tmp=mul[n];
tmp=tmp*inv[m]%mod;
tmp=tmp*inv[n-m]%mod;
return tmp;
}
int main()
{
n=read(),m=read();
if (m==){printf("0\n");return ;}
Lim=max(n,m)+;
mul[]=;inv[]=;inv[]=;
for (int i=;i<=Lim;i++) mul[i]=mul[i-]*i%mod;
for (int i=;i<=Lim;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for (int i=;i<=Lim;i++) inv[i]=inv[i]*inv[i-]%mod;
Lim=min(m-,n-);
for (int i=;i<=Lim;i++)
{
int lim=(n-i)/,Max;
Max=i+lim-;
ans=(ans+C(Max+,i+)*)%mod;
if ((n-i)%==) ans=(ans-C(Max,i))%mod;
}
ans=(ans-(Lim+)+min(n,m))%mod;
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
04-15 07:54