G8022 [GESP202606 八级] 堆石子 题解

知识点：组合数学、隔板法、模逆元、快速幂。

解题思路

将n颗石子分为m个有序非空堆，隔板法得到C(n-1,m-1)。用连乘计算分子分母，并通过快速幂求分母模逆元。

为什么正确

在n颗石子之间n-1个间隔中选m-1处切开，与每个正整数组合一一对应，因此是所需组合数。

易错点

m>n无解为0；非空堆要求不能使用C(n+m-1,m-1)，模数10^9+7且分母范围按题目保证可逆。

复杂度

时间O(m+log M)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m,n;
    cin>>m>>n;
    if(m>n) {
        cout<<0;
        return 0;
    }
    const long long M=1000000007;
    auto pw=[&](long long a,long long b) {
        long long v=1;
        while(b) {
            if(b&1)v=v*a%M;
            a=a*a%M;
            b>>=1;
        }
        return v;
    }
    ;
    long long num=1,den=1;
    for(int i=1;i<m;i++) {
        num=num*(n-i)%M;
        den=den*i%M;
    }
    cout<<num*pw(den,M-2)%M;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。