跳到主要内容

隔板法

  1. 求线性不定方程的整数解的组数
  2. 求相同元素分组的方案数

1.正整数和的组数​

若xi>=1x_i>=1,求x1+x2+...+xk=nx_1+x_2+...+x_k=n的整数解的组数，可以看成有n个小球，然后让你分成k组，有多少种分法？这n个小球有n-1个空位，现在需要插入k-1个板子，就可以分好，答案为Cn−1k−1C_{n-1}^{k-1}

2.非负整数和的组数​

若xi>=0x_i>=0，求x1+x2+...+xk=nx_1+x_2+...+x_k=n的整数解的组数。 可以令yi=xi+1,则yi>=1y_i=x_i+1,则y_i>=1,就可以转换为：y1+y2+...+yk=n+ky_1+y_2+...+y_k=n+k,答案为Cn+k−1k−1C_{n+k-1}^{k-1}

3.不同下届整数和的组数​

求x1+x2+...+xk=nx_1+x_2+...+x_k=n的整数解的组数，其中xi>=ai>=0，∑ai<=nx_i>=a_i>=0，\sum a_i<=n. 可以令yi=xi−ai+1,则yi>=1y_i=x_i-a_i+1,则y_i>=1,那么y1+y2+...+yk=n−∑ai+ky_1+y_2+...+y_k=n-\sum a_i+k，答案为:Cn−∑ai+k−1k−1C_{n- \sum a_i+k-1}^{k-1}

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 150,mod=1000;

int x,k;
int c[1000][100][N];
//三维，第三维代表高精度的每一个数字

int qmi(int a,int k,int p){
    int res=1;
    while (k){
        if (k&1) res=res*a%p;
        a=a*a%p;
        k>>=1;
    }
    return res;
}

//把a，b加到c里面
void add(int c[],int a[],int b[]){
    for(int i=0;i<N-1;i++){
        c[i]+=a[i]+b[i];
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
}

void getC(int n,int k){
    for(int i=0;i<n;i++){
        for(int j=0;j<=i&&j<k;j++){
            if (!j) c[i][j][0]=1;
            else add(c[i][j],c[i-1][j],c[i-1][j-1]);
        }
    }
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>k>>x;
    int n=qmi(x%mod,x,mod);
    getC(n,k);
    int i=N-1;
    //隔板法计算的结果就是C_{n-1}^{k-1}
    while (c[n-1][k-1][i]==0)i--;
    while (i>=0) {
        cout<<c[n-1][k-1][i];
        i--;
    }

    return 0;
}

0%