文章导读

Feb. 5th 总结 | 组合数学

DRheEheAM_Gary 2026-02-05 11

每日 Ad-hoc

P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

遇事不决先打表((

注意到当 $a$ 为奇数时存在构造 $[a\ , \ 1\ ,\ 2\ ,\ 2+a]$
将构造整体乘 $2^k\ (k\in\N)$ 仍成立。
得到通解。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        int a;
        cin>>a;
        int t=1;
        while (a%2==0) t*=2,a/=2;
        cout<<t<<" "<<2*t<<" "<<t*(2+a)<<"\n";
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        int a;
        cin>>a;
        int t=1;
        while (a%2==0) t*=2,a/=2;
        cout<<t<<" "<<2*t<<" "<<t*(2+a)<<"\n";
    }
    return 0;
}

组合数学

卢卡斯定理（Lucas’ Theorem）

\large C_n^m\equiv C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\times C_{n\ \bmod\ p}^{m\ \bmod\ p}\pmod p

证明：

引理 $1$ : $\large C_p^k\equiv0\ (\text{mod}\ p)$ ，易证。

引理 $2$ : $(1+x)^p\equiv 1+x^p \ \pmod p$ ，读者自证不难。

~~这样真的好吗~~

接下来：
设 $n=pa+b\ ,\ m=pc+d$
所以：

\large \begin{aligned} (1+x)^n &= (1+x)^{pa}(1+x)^b \\ &= (1+x^p)^a(1+x)^b \\ &= \sum_{i=1}^{a}C_a^ix^{pi}\sum_{i=1}^{b}C_b^ix^i \end{aligned}

根据二项式定理：

\large \begin{aligned} (1+x)^n &= \sum_{i=1}^{n}C_n^ix^i \end{aligned}

所以对于 $x^m$ 这个项，系数为 $C_n^m$ 。
但是 $m=pc+d$ 所以 $x^m=x^{pc}x^d$

前者在第一个式子中系数为 $C_a^c$ ，而后者为 $C_b^d$ 。

代回 $a,b,c,d$ 得证。

模版题：

P3807 【模板】卢卡斯定理 / Lucas 定理

代码：

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int f[N],g[N];
int qpow (int a,int b,int p) {
    int res=1;
    while (b) {
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
void slove (int n,int m,int p) {
    f[0]=g[0]=1;
    for (int i=1;i<=n+m;i++) {
        f[i]=f[i-1]*i%p;
        g[i]=g[i-1]*qpow(i,p-2,p)%p;
    }
}
int getc (int n,int m,int p) {
    if (m>n) return 0;
    return f[n]*g[m]*g[n-m]%p;
}
int lucas (int n,int m,int p) {
    if (m==0) return 1;
    return lucas(n/p,m/p,p)*getc(n%p,m%p,p)%p;
}
signed main() {
    Cios;
    int q;
    cin>>q;
    while (q--) {
        int n,m,p;
        cin>>n>>m>>p;
        slove(n,m,p);
        cout<<lucas(n+m,n,p)<<"\n";
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int f[N],g[N];
int qpow (int a,int b,int p) {
    int res=1;
    while (b) {
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
void slove (int n,int m,int p) {
    f[0]=g[0]=1;
    for (int i=1;i<=n+m;i++) {
        f[i]=f[i-1]*i%p;
        g[i]=g[i-1]*qpow(i,p-2,p)%p;
    }
}
int getc (int n,int m,int p) {
    if (m>n) return 0;
    return f[n]*g[m]*g[n-m]%p;
}
int lucas (int n,int m,int p) {
    if (m==0) return 1;
    return lucas(n/p,m/p,p)*getc(n%p,m%p,p)%p;
}
signed main() {
    Cios;
    int q;
    cin>>q;
    while (q--) {
        int n,m,p;
        cin>>n>>m>>p;
        slove(n,m,p);
        cout<<lucas(n+m,n,p)<<"\n";
    }
    return 0;
}

插板法

我感觉我好想写过一次…

插板法（Stars and bars）是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。

1. 正整数和的数目

考虑拿 $k-1$ 块板子插入到 $n$ 个元素两两形成的 $n-1$ 个空里面。
因为元素是完全相同的，所以答案就是 $C_{n-1}^{k-1}$ 。
本质是求 $x_1+x_2+x_3+\cdots+x_k=n$ 的正整数解的组数．

2. 非负整数和的数目

我们将问题 1 转换一下，给每个元素加上 $1$ 。

那么总和 $n$ 就变为了 $n+k$ 。

再使用原公式，答案即为 $C_{n+k-1}^{k-1}=C_{n+k-1}^{n}$

3. 不同下界整数和的数目

我们让每个元素减去自己的下界 $a_i$

则 $n\to n-\sum a_i$

继续使用原公式得到答案 $C_{n-\sum a+k-1}^{n-\sum a}$

例题：

P1771 方程的解

代码：

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10;
int vis[N],c[N];
vector<int> pr;
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) res=(res*a)%1000;
        a=(a*a)%1000;
        b>>=1;
    }
    return res;
}
void getp (int n) {
    for (int i=2;i<=n;i++) {
        if (!vis[i]) pr.push_back(i);
        vis[i]=1;
        for (int j=0;pr[j]*i<=n;j++) {
            vis[pr[j]*i]=1;
            if (i%pr[j]==0) break;
        }
    }
}
int count (int n,int p) {
    int res=0;
    while (n) res+=n/p,n/=p;
    return res;
}
int sum (int n,int m,int p) {
    return count(n,p)-count(m,p)-count(n-m,p);
}
void mul (int p,int& len) {
    int tmp=0;
    for (int i=0;i<len;i++) {
        tmp+=c[i]*p;
        c[i]=tmp%10;
        tmp/=10;
    }
    while (tmp) {
        c[len++]=tmp%10;
        tmp/=10;
    }
}
signed main() {
    Cios;
    // int n,m;
    // cin>>n>>m;
    int k,x;
    cin>>k>>x;
    int n,m;
    m=k-1;
    n=qpow(x,x)-1;
    getp(n);
    int len=1;
    c[0]=1;
    for (int p:pr) {
        int tmp=sum(n,m,p);
        while (tmp--) mul(p,len);
    }
    for (int i=len-1;i>=0;i--) cout<<c[i];
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10;
int vis[N],c[N];
vector<int> pr;
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) res=(res*a)%1000;
        a=(a*a)%1000;
        b>>=1;
    }
    return res;
}
void getp (int n) {
    for (int i=2;i<=n;i++) {
        if (!vis[i]) pr.push_back(i);
        vis[i]=1;
        for (int j=0;pr[j]*i<=n;j++) {
            vis[pr[j]*i]=1;
            if (i%pr[j]==0) break;
        }
    }
}
int count (int n,int p) {
    int res=0;
    while (n) res+=n/p,n/=p;
    return res;
}
int sum (int n,int m,int p) {
    return count(n,p)-count(m,p)-count(n-m,p);
}
void mul (int p,int& len) {
    int tmp=0;
    for (int i=0;i<len;i++) {
        tmp+=c[i]*p;
        c[i]=tmp%10;
        tmp/=10;
    }
    while (tmp) {
        c[len++]=tmp%10;
        tmp/=10;
    }
}
signed main() {
    Cios;
    // int n,m;
    // cin>>n>>m;
    int k,x;
    cin>>k>>x;
    int n,m;
    m=k-1;
    n=qpow(x,x)-1;
    getp(n);
    int len=1;
    c[0]=1;
    for (int p:pr) {
        int tmp=sum(n,m,p);
        while (tmp--) mul(p,len);
    }
    for (int i=len-1;i>=0;i--) cout<<c[i];
    return 0;
}

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

[填写昵称邮箱后可以评论]

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 5th 总结 | 组合数学

每日 Ad-hoc

P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

组合数学

卢卡斯定理（Lucas’ Theorem）

P3807 【模板】卢卡斯定理 / Lucas 定理

插板法

P1771 方程的解

评论（0）

发表评论取消回复

插入代码

DRheEheAM_Gary Blog

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 5th 总结 | 组合数学

每日 Ad-hoc

P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

组合数学

卢卡斯定理 （Lucas’ Theorem）

P3807 【模板】卢卡斯定理 / Lucas 定理

插板法

P1771 方程的解

评论（0）

发表评论 取消回复

插入代码

DRheEheAM_Gary Blog

卢卡斯定理（Lucas’ Theorem）

发表评论取消回复