LUOGU P1680 奇怪的分组

题目背景

终于解出了dm同学的难题，dm同学同意帮v神联络。可dm同学有个习惯，就是联络同学的时候喜欢分组联络，而且分组的方式也很特别，要求第i组的的人数必须大于他指定的个数ci。在dm同学联络的时候，v神在想，按照dm同学的规则一共可以有多少种方案呢？他想啊想,终于……没想出来。于是他又想到了聪明的你，你能帮v神算出按照dm同学的规则有多少种分组方案吗？

题目描述

v神的班级共有n个人，dm同学想把同学分成M组联络，要求第i组的人数必须大于给定的正整数Ci，求有多少不同的方案？（两个是相同的方案当且仅当对于任意的一队i，两个方案的第i组同学数量相等）由于结果很大，所以你只需要输出模1000000007的值。

输入输出格式

输入格式：

第一行两个整数N和M ，后面有M行，每行一个整数，表示Ci

输出格式：

仅有一行，一个整数，方案数模1000000007的值。

输入输出样例

输入样例#1：复制

10 3

1

2

3

输出样例#1：复制

说明

样例解释：

方案有三种，每组的个数分别是（3,3,4），（2,4,4），（2,3,5）。

数据范围约定：

对于30%的数据，N ,M<= 10

对于60%的数据，N ,M<=1000

对于100%的数据，N ,M<= 1000000 Ci<=1000

数据保证至少有一个方案

解题思路

本来是道sb题，硬生生搞了1个小时，相当于隔板法，每个先填c[i]+1个，然后剩余k个，相当于把k个苹果塞到m个盒子里，盒子可以为空，方案数为C(n+m-1,m-1)。还有一种理解方式是每个先填c[i]个，剩kk个，把kk个苹果塞到m个盒子里，盒子不能为空，方案数为C(n-1,m-1) 。然后费马小定理算出逆元。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

const int MAXN = 1000005;

const int mod = 1e9+7;

typedef long long LL;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?-1:1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,m;

LL ans,to[MAXN<<2]={0,1};

LL fast_pow(LL x,int y){

    LL ret=1;

    for(;y;y>>=1){

        if(y&1) ret=ret*x%mod;

        x=x*x%mod;

    }

    return ret;

}

int main(){

    for(register int i=2;i<=2000000;i++) to[i]=to[i-1]*i%mod;

    n=rd();m=rd();

    for(register int i=1;i<=m;i++) n-=rd()+1;

    if(m==1 || n==0) {cout<<1<<endl;return 0;}

    ans=to[n+m-1]*fast_pow(to[m-1],mod-2)%mod*fast_pow(to[n],mod-2)%mod;

    cout<<ans%mod<<endl;

    return 0;

}

巴特西

LUOGU P1680 奇怪的分组

解题思路

代码

最新文章

热门文章