典型的插板问题

· · 题解

传送门

草率审题

看到这种题目，读入两个数，输出一个数，显然是打表找规律！

但是，我们通过打表，没有发现什么规律。

于是我们可以想想数论方面的东西。

分析

我们先对着题目盯上个一分钟，肯定能发现什么蹊跷。

其实题目就是求k个正整数的和是g(x)的方案数嘛。

我们假设，现场有g(x)个苹果，你要分成k份……

这不就是一个典型的插板问题么？

所以我们这g(x)个苹果之间，就有了g(x)-1个空隙。

我们要把苹果分成k个部分，所以就要用上k-1个空隙。

所以……答案就是\textrm{C}_{x^x \mod 1000-1}^{k-1}

解法

我们再看看数据范围 k \leq 100

那么k!一定会炸掉，所以我们就要高精度！

然后组合数学公式又涉及到了除法，所以我们可以用高精除单精的方法。

当然，我们也是可以分解质因数的。

代码

#include<cstdio>
#define inf 1000
#define ll long long
ll n,m,s[1000],t;
ll ksm(ll k,ll t)//快速幂，不解释 
{
    ll s=1;
    for (;t;)
    {
        if (t%2==1) s*=k,s%=inf;
        k*=k%inf,k%=inf,t/=2;
    }
    return s%inf;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    m%=inf,m=ksm(m,m)-1,n--;//数字的初始化 
    t=s[1]=1;//高精度初始化 
    for (int i=m;i>m-n;i--)//高精乘 
    {
        int x=0;//保存进位 
        for (int j=1;j<=t;j++) s[j]=i*s[j]+x,x=s[j]/10,s[j]%=10;//逐位相乘 
        for (;x;) s[++t]=x%10,x/=10;//进位 
    }
    for (int i=2;i<=n;i++)//高精除单精 
    {
        int x=0;//保存计算中的余数 
        for (int j=t;j;j--)//逐位相除 
        {
            int r=s[j]+x*10;
            s[j]=r/i;
            x=r%i;
        }
        for (;!s[t];t--);//把多余的位数删掉 
    }
    for (int i=t;i;i--) printf("%lld",s[i]);
    return 0;
}