【BZOJ4402】Claris的剑（组合计数）

题意：

给定数列的定义：

1.每个元素都是正整数

2.每个元素不能超过M

3.相邻两个元素的差的绝对值必须是1

4.第一个元素的值必须是1

求有多少个长度不超过N的合法的本质不同的序列

两个序列本质不同，当且仅当存在至少一个数值，在两个序列中出现次数不一样

比如{1,2,3}和{1,3,2}是本质相同的

{1,2,3}和{1,2,1}则是本质不同的

答案对1e9+7取模

N,M<=2e6

思路：From https://blog.csdn.net/ws_yzy/article/details/50753724

 #include<cstdio>

 typedef long long ll;

 using namespace std;

 #define MOD 1000000007

 #define N 2100000

 ll fac[N],inv[N]; 

 ll c(int x,int y)

 {

     return fac[x]*inv[y]%MOD*inv[x-y]%MOD;

 }

 ll calc(int x,int y)

 {

     if(x<) return ;

     if(x==||x==) return ;

     return c(x/+y,y);

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     fac[]=;

     for(int i=;i<=n;i++) fac[i]=fac[i-]*i%MOD;

     inv[]=inv[]=;

     for(int i=;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;

     for(int i=;i<=n;i++) inv[i]=inv[i]*inv[i-]%MOD;

     ll ans=;

     if(n&&m) ans++;

     for(int i=;i<=m;i++)

     {

         ans=(ans+calc(n-i,i-))%MOD;

         ans=(ans+calc(n-i-,i-))%MOD;

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

【BZOJ4402】Claris的剑（组合计数）

最新文章

热门文章