隔板法

例一:

例二：

E. 分装组合

Description

老师交给小H 一个任务：有

Input

只有一行，两个非负整数

Output

1 个非负整数

Samples

Input Copy

5 3

Output

这个题就是每个箱子至少放一个球，然后你可以转化为每一个箱子先放一个球，然后就转化为有n-m个球然后，放在m个箱子

中（允许箱子为空的），和上面是一样的

例三：

小王在考试中遇到一道难题：方程

Input

一行，两个以空格隔开的数

Output

一行，一个数，表示非负整数解的个数。

Samples

Input Copy

3 4

Output

Hint

样例说明：

0,0,4 0,1,3 0,2,2 0,3,1 0,4,0

1,0,3 1,1,2 1,2,1 1,3,0

2,0,2 2,1,1 2,2,0

3,0,1 3,1,0

4,0,0

(total=5+4+3+2+1=15)

数据范围

对于50 %的数据，
对于100 %的数据，

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100; 
const int mod=1000000007;
ll f[maxn];
int n,m;
void inint(){
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=1000000;i++){
        f[i]=(f[i-1]*i)%mod;
    }
}
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b/=2;
    }
    return ans%mod;
}
ll C(int n,int m){
    if(m==0) return 1;
    return (f[n]*qpow(f[n-m]*f[m]%mod,mod-2)%mod)%mod;
}
int main(){
    inint();
    cin>>n>>m;
    cout<<C(m+n-1,n-1)<<endl;
}

例四：

链接：https://ac.nowcoder.com/acm/contest/1085/J
来源：牛客网

小sun最近对计数问题来了兴趣，现在他有一个问题想问问你：

有一个含有n个数字的序列，每个数的大小是不超过1000的正整数，同时这个序列是个单调不增序列。但是很不幸的是，序列在保存过程中有些数字丢失了，请你根据上述条件，计算出有多少种不同的序列满足上述条件，答案对1000000007取模。（具体可以看样例）

输入描述:

第一行包含一个整数n，表示这个序列的长度。

第二行为n个整数

aia_iai​，用空格隔开，如果数字是0，代表这个数字丢失了，其他的数字都在1~1000之间

输出描述:

输出一行，表示答案。

示例1

输入

复制

3
9 0 8

输出

复制

示例2

输入

复制

2
5 4

输出

复制

示例3

输入

复制

3
0 0 0

输出

复制

167167000

备注:

隔板法：

隔板法就是在n个元素间插入（b-1）个板，即把n个元素分成b组的方法。

比如将20个大小形状完全相同的小球放入3个不同的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？

解析：将20个小球分成三组需要两块隔板，因为允许有盒子为空，不符合隔板法的原理，那就人为的再加上3个小球，保证每个盒子都至少分到一个小球，那就符合隔板法的要求了（分完后，再在每组中各去掉一个小球，即满足了题设的要求）。然后就变成待分小球总数为23个，球中间有22个空档，需要在这22个空档里加入2个隔板来分隔为3份，共有 $C_{22}^{2}$ = 231种不同的方法。

回到本题，对于栗子9 0 0 7，我们可以使用的数字是9 - 7 + 1 = 3个（7，8，9），我们把可使用的数字当成盒子，把丢失的数字当成小球，是不是和上面的栗子一样了，那么答案也就是 $C_{n+m-1}^{m-1}$ （n表示丢失数字的个数，m表示可使用的数字）。想想为什么不把可使用的数字当成球，丢失的数字当成盒子呢？其实是因为可以出现重复的数字，举个栗子9，0，0，8，答案为3，可使用的数字为2，丢失的数字也是2，每种情况如下（下面的小球表示零，也就是丢失的数字）：

9，9，9，8（将两个小球放9号盒子里）
9，9，8，8（将两个小球分别放到8号和9号盒子里）
9，8，8，8（将两个小球放8号盒子里）

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100; 
const int mod=1000000007;
ll f[maxn];
int a[maxn];
int n;
void inint(){
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=1000000;i++){
        f[i]=(f[i-1]*i)%mod;
    }
}
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b/=2;
    }
    return ans%mod;
}
ll C(int n,int m){
    if(m==0) return 1;
    return (f[n]*qpow(f[n-m]*f[m]%mod,mod-2)%mod)%mod;
}
int main(){
    inint();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cnt=0,id=0;
    ll ans=1;
    a[0]=1000;
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            cnt++;
        }
        else{
            int n=cnt;
            int m=a[id]-a[i]+1;
            id=i;
            cnt=0;
            ans=ans*(C(n+m-1,m-1)%mod)%mod;
            //cout<<n<<" "<<m<<" "<<ans<<endl;
        }
    }
    if(cnt){
        int n=cnt,m=a[id];
        ans=ans*C(n+m-1,m-1)%mod;
    }
    cout<<ans%mod<<endl;
}

例题：

视频讲解

传送门

给你一个二维整数数组 queries ，其中 queries[i] = [ni, ki] 。第 i 个查询 queries[i] 要求构造长度为 ni 、每个元素都是正整数的数组，且满足所有元素的乘积为 ki ，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 109 + 7 取余。

请你返回一个整数数组 answer，满足 answer.length == queries.length ，其中 answer[i]是第 i 个查询的结果。

示例 1：

输入：queries = [[2,6],[5,1],[73,660]]
输出：[4,1,50734910]
解释：每个查询之间彼此独立。
[2,6]：总共有 4 种方案得到长度为 2 且乘积为 6 的数组：[1,6]，[2,3]，[3,2]，[6,1]。
[5,1]：总共有 1 种方案得到长度为 5 且乘积为 1 的数组：[1,1,1,1,1]。
[73,660]：总共有 1050734917 种方案得到长度为 73 且乘积为 660 的数组。1050734917 对 109 + 7 取余得到 50734910 。
示例 2 ：

输入：queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：[1,2,3,10,5]

提示：

1 <= queries.length <= 1e4
1 <= ni, ki <= 1e4

这个题的意思就是问给你一个m能分成多少个n个数的乘积

这个题不用担心没有结果哈，因为可以分成1的

我们知道s个球分到n个盒子里面的方案数为

C(n + s - 1, n - 1)

我们对m进行质因子分解为m=p1^a1*p2^a2---------

对于每一个p1可以看成把a1放在n个盒子中，最后对于不同的质因子有不同符合乘法原则

typedef long long ll;
const int mod=1e9+7;
const int maxn=1e4+100;
class Solution {
public:
    int f[maxn],g[maxn];
    int qpow(int a,int b){
        int ans=1;
        while(b){
            if(b&1){
                ans=(ll)ans * a%mod;
            }
            a=(ll)a * a%mod;
            b>>=1;
        }
        return ans;
    }
    int C(int a,int b){
        return (ll)f[a] * g[b] % mod * g[a - b] % mod;
    }
    vector<int> waysToFillArray(vector<vector<int>>& queries) {
        f[0] = g[0] = 1;
        for (int i = 1; i < maxn; i ++ ) {
            f[i] = (ll)f[i - 1] * i % mod;
            g[i] = qpow(f[i], mod - 2);
        }
        vector<int>v;
        for(auto &q: queries){
            int n=q[0],m=q[1];
            int res=1;
            for (int i = 2; i * i <= m; i ++ ) {
                if (m % i == 0) {
                    int s = 0;
                    while (m % i == 0) s ++ , m /= i;
                    res = (ll)res * C(n + s - 1, n - 1) % mod;
                }
            }
            if (m > 1) res = (ll)res * C(n, n - 1) % mod;
            v.push_back(res);
        }
        return v;
    }
};