你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

洛谷 P1680 奇怪的分组

2021-11-11 20:50:55

:v 神的班级共有 N 个人,dm 同学想把同学们分成 M 组联络,要求第 i组的人数必须大于给定的正整数 ,输出有多少种不同的方案。

10 3
1
2
3
3

看了标签以为只是个简单的贪心,没想到涉及到这么多数论的知识。
1.组合数学:先给每组分配给定的正整数,得出剩下的人数n,把这些人数分配给m组。可以运用隔板法,把这些人分割开需要n-1个板子,把它们分割为m组需要插入m-1个板子。这就转化为在n-1个空位中选m-1个进行插入,则方案数就是C(n-1,m-1)(无序),利用排列组合公式即可算出。
2.费马小定理:这个题的方案数有可能很大,要对答案取1e9+7的模。但是运用排列组合公式会形成a/b%mod的形式,除数取模会损失精度,使答案错误。所以需要对分母b进行逆元,逆元的概念:
https://www.jianshu.com/p/e9e1c52bf6c9
因为1e9+7是质数,所以用费马小定理求逆元更方便,b的逆元即b的mod-2次幂,转化为a*b(mod-2次方)%mod即可求出答案。
3.快速幂:1e9+5次幂必然超时,用快速幂复杂度很低,模板:

int fastpow(int a,int n)
{    if(n==1) return a;
     int temp=fastpow(a,n/2);
     if(n%2==1) return temp*temp*a;
     else  return temp*temp;
}

这种数论的题没咋做,加上我比较菜,学了这些数论的知识代码还捣鼓到了半夜…

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long LL;
LL a[1000001];
LL f[1000010];

LL fastpow(LL b,LL n)   //快速幂
{
     if(n==1) return b;
     LL temp=fastpow(b,n/2);
     if(n%2==1) return temp*temp%mod*b%mod;
     else return temp*temp%mod;
}
LL s(LL m,LL n)
{
     LL r=(f[m-n]*f[n])%mod;  //分母求逆元
     return f[m]*fastpow(r,mod-2)%mod;  //求答案
}
int main()
{
    LL i,j,m,n;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>a[i];
        n=n-a[i];
    }
    f[0]=1;
    for(i=1;i<=1000010;i++)
    {
        f[i]=(f[i-1]*i)%mod;  //提前把阶乘打出来
    }
    cout<<s(n-1,m-1)<<endl;
    return 0;
}

wr了好几次,主要有两点:
1.因为mod的幂很大,有些数需要设成long long,干脆typedef一个long long把所有变量都改成ll,这样省的因为某个int让答案报错。
2.因为需要很多数学公式会产生很多超过mod的数,要及时的取余,我就因为少一个mod找了好久…