组合数学--母函数

约定不等于承诺〃 2023-06-03 13:52 28阅读 0赞

模板：（转载：[https://blog.csdn.net/xiaofei\_it/article/details/17042651][https_blog.csdn.net_xiaofei_it_article_details_17042651]）

//为计算结果，b为中间结果。
    int a[MAX],b[MAX];
    //初始化a
    memset(a,0,sizeof(a));
    a[0]=1;
    for (int i=1;i<=17;i++)//循环每个因子
    {
        memset(b,0,sizeof(b));
        for (int j=n1[i];j<=n2[i]&&j*v[i]<=P;j++)//循环每个因子的每一项
            for (int k=0;k+j*v[i]<=P;k++)//循环a的每个项
                b[k+j*v[i]]+=a[k];//把结果加到对应位
        memcpy(a,b,sizeof(b));//b赋值给a
    }

//模板二
    //初始化a，因为有last，所以这里无需初始化其他位
    a[0]=1;
    int last=0;
    for (int i=0;i<K;i++)
    {
        int last2=min(last+n[i]*v[i],P);//计算下一次的last
        memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2]
        for (int j=n1[i];j<=n2[i]&&j*v[i]<=last2;j++)//这里是last2
            for (int k=0;k<=last&&k+j*v[i]<=last2;k++)//这里一个是last，一个是last2
                b[k+j*v[i]]+=a[k];
        memcpy(a,b,sizeof(int)*(last2+1));//b赋值给a，只赋值0..last2
        last=last2;//更新last
    }

HDU：1085

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn]={
         0,1,2,5};
    int n1[]={
         0,0,0,0};
    int p,K;
    void muhs2(){
        a[0]=1;
        int last=0;
        for(int i=1;i<=3;i++){
            int last2=last+n2[i]*v[i];
            memset(b,0,sizeof(int)*(last2+1));
            for(int j=n1[i];j<=n2[i];j++){
                for(int k=0;k<=last;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(int)*(last2+1));
            last=last2;
        }
    }
    int main(){
        while(cin>>n2[1]>>n2[2]>>n2[3]){
            if(n2[1]+n2[2]+n2[3]==0)break;
            memset(a,0,sizeof(a));
            muhs2();
            int i=1;
            while(a[i]){
                i++;
            }
            cout<<i<<endl;
        }
    
        return 0;
    }

HDU:1171

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=2e6+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn];
    int n1[maxn]={
         0};
    int n,p;
    void muhs2(){
        a[0]=1;
        int last=0;
        for(int i=1;i<=n;i++){
            int last2=last+n2[i]*v[i];
            memset(b,0,sizeof(int)*(last2+1));
            for(int j=n1[i];j<=n2[i];j++){
                for(int k=0;k<=last;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(int)*(last2+1));
            last=last2;
        }
        int i=last/2;
        while(a[i]==0&&i>=0)i--;
        cout<<last-i<<' '<<i<<endl;
    }
    int main(){
        while(cin>>n){
            if(n<=0)break;
            memset(a,0,sizeof(a));
            for(int i=1;i<=n;i++){
                cin>>v[i]>>n2[i];
            }
            muhs2();
        }
    
        return 0;
    }

HDU:1398

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e4+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn];
    int n1[maxn]={
         0};
    int n,p;
    void muhs1(){
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=17;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j*v[i]<=n;j++){
                for(int k=0;k+j*v[i]<=n;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(b));
        }
        cout<<a[n]<<endl;
    }
    void init(){
        for(int i=1;i<=17;i++)v[i]=i*i;
    }
    int main(){
        init();
        while(cin>>n){
            if(n==0)break;
            memset(a,0,sizeof(a));
            muhs1();
        }
    
        return 0;
    }

HDU:2079

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e4+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn];
    int n1[maxn]={
         0};
    int n,m,p;
    void muhs1(){
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=m;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j*v[i]<=n&&j<=n2[i];j++){
                for(int k=0;k+j*v[i]<=n;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(b));
        }
        cout<<a[n]<<endl;
    }
    int main(){
        int T;
        cin>>T;
        while(T--){
            cin>>n>>m;
            for(int i=1;i<=m;i++){
                cin>>v[i]>>n2[i];
            }
            muhs1();
        }
    
        return 0;
    }

HDU:2082

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e4+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn];
    int n1[maxn]={
         0};
    int n,m,p=50;
    void muhs1(){
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=26;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j*v[i]<=p&&j<=n2[i];j++){
                for(int k=0;k+j*v[i]<=p;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(b));
        }
    }
    int main(){
        int T;
        cin>>T;
        while(T--){
            for(int i=1;i<=26;i++){
                v[i]=i;
                cin>>n2[i];
            }
            muhs1();
            ll ans=0;
            for(int i=1;i<=50;i++){
                ans+=a[i]*1LL;
            }
            cout<<ans<<endl;
        }
    
        return 0;
    }

HDU:2110

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn];
    int n1[maxn]={
         0};
    int n,m,p=50,sum;
    void muhs1(){
        a[0]=1;
        int last=0;
        for(int i=1;i<=n;i++){
            int last2=min(last+n2[i]*v[i],sum);
            memset(b,0,sizeof(int)*(last2+1));
            for(int j=0;j<=n2[i]&&j*v[i]<=last2;j++){
                for(int k=0;k<=last&&k+j*v[i]<=last2;k++){
                    b[k+j*v[i]]+=a[k];
                    b[k+j*v[i]]%=10000;
                }
            }
            memcpy(a,b,sizeof(int)*(last2+1));
            last=last2;
        }
        if(a[sum]>0)cout<<a[sum]%10000<<endl;
        else cout<<"sorry"<<endl;
    }
    int main(){
        while(cin>>n){
            if(n==0)break;
            memset(a,0,sizeof(a));
            sum=0;
            for(int i=1;i<=n;i++){
                cin>>v[i]>>n2[i];
                sum+=(v[i]*n2[i]);
            }
            if(sum%3){
                cout<<"sorry"<<endl;
                continue;
            }
            sum/=3;
            muhs1();
        }
    
        return 0;
    }

HDU:2152

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn];
    int n1[maxn];
    int n,m,p=50;
    void muhs1(){
        a[0]=1;
        int last=0;
        for(int i=1;i<=n;i++){
            int last2=min(last+n2[i]*v[i],m);
            memset(b,0,sizeof(int)*(last2+1));
            for(int j=n1[i];j<=n2[i]&&j*v[i]<=last2;j++){
                for(int k=0;k<=last&&k+j*v[i]<=last2;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(int)*(last2+1));
            last=last2;
        }
        if(last<m)cout<<0<<endl;
        else cout<<a[m]<<endl;
    }
    int main(){
        while(cin>>n>>m){
            for(int i=1;i<=n;i++){
                v[i]=1;
                cin>>n1[i]>>n2[i];
            }
            muhs1();
    
        }
    
        return 0;
    }

HDU：1284

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    const int inf=0x3f3f3f3f;
    int a[maxn],b[maxn];
    int n2[maxn];
    int v[maxn]={
         0,1,2,3};
    int n1[maxn];
    int n,m,p=50;
    void muhs1(){
        a[0]=1;
        n=32768;
        int last=0;
        for(int i=1;i<=3;i++){
            int last2=n;
            memset(b,0,sizeof(int)*(last2+1));
            for(int j=0;j*v[i]<=last2;j++){
                for(int k=0;k<=last&&k+j*v[i]<=last2;k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a,b,sizeof(int)*(last2+1));
            last=last2;
        }
    }
    int main(){
        muhs1();
        while(cin>>n){
            cout<<a[n]<<endl;
        }
    
        return 0;
    }

HDU：2189

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=160;
    int n,m;
    int a[maxn],b[maxn];
    int prime[maxn];
    void getprime(){
        memset(prime,0,sizeof(prime));
        for(int i=2;i<=150;i++){
            if(!prime[i])prime[++prime[0]]=i;
            for(int j=1;j<=prime[0]&&prime[j]<=150/i;j++){
                prime[prime[j]*i]=1;
                if(i%prime[j]==0)break;
            }
        }
    }
    void muhs(){
        memset(a,0,sizeof(a));
        for(int i=0;i<=n;i+=2)a[i]=1;
        for(int i=2;i<=prime[0];i++){
            memset(b,0,sizeof(b));
            for(int j=0;j<=150;j++){
                for(int k=0;k+j<=n;k+=prime[i]){
                    b[k+j]+=a[j];
                }
            }
            memcpy(a,b,sizeof(b));
        }
    
    }
    int main(){
        getprime();
        int T;
        cin>>T;
        while(T--){
            cin>>n;
            muhs();
            cout<<a[n]<<endl;
        }
    }

HDU:2065

指数型母函数，根据泰勒展开（虽然还不懂……）最终答案为2^(n-1)+4^(n-1)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=160;
    const int mod=100;
    ll n;
    int a[maxn],b[maxn];
    ll ksm(ll a,ll b){
        ll ans=1;
        while(b){
            if(b&1){
                ans=(ans*(a%mod))%mod;
            }
            b>>=1;
            a=((a%mod)*(a%mod))%mod;
            ans%=mod;
        }
        return ans%mod;
    }
    
    int main(){
        int T;
        while(cin>>T){
            if(T==0)break;
            int flag=1;
            while(T--){
                cin>>n;
                cout<<"Case "<<flag++<<": ";
                cout<<(ksm(2,n-1)+ksm(4,n-1))%mod<<endl;
            }
            cout<<endl;
        }
    
    }

POJ：3734

跟上题一样，泰勒展开

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    using namespace std;
    typedef long long ll;
    const int maxn=160;
    const int mod=10007;
    ll n;
    int a[maxn],b[maxn];
    ll ksm(ll a,ll b){
        ll ans=1;
        while(b){
            if(b&1){
                ans=(ans*(a%mod))%mod;
            }
            b>>=1;
            a=((a%mod)*(a%mod))%mod;
            ans%=mod;
        }
        return ans%mod;
    }
    
    int main(){
        int T;
        cin>>T;
        while(T--){
            cin>>n;
            cout<<(ksm(2,n-1)+ksm(4,n-1))%mod<<endl;
        }
    
    }

HDU:1709

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e4+10;
    int n;
    int a[maxn],b[maxn],v[maxn];
    int ans[maxn];
    int sum=0;
    void muhs(){
        memset(a,0,sizeof(a));
        a[v[1]]=1;
        a[0]=1;
        for(int i=2;i<=n;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j<=sum;j++){
                if(b[j]==1||a[j]==1)b[j]=1;
                if(a[j]==1)b[j+v[i]]=b[abs(j-v[i])]=1;
            }
            memcpy(a,b,sizeof(b));
        }
        /*for(int i=1;i<=sum;i++)cout<<a[i]<<' ';
        cout<<endl;*/
    }
    int main(){
        ios::sync_with_stdio(false);
        while(cin>>n){
            sum=0;
            for(int i=1;i<=n;i++){
                cin>>v[i];
                sum+=v[i];
            }
            muhs();
            int tot=0;
            for(int i=1;i<=sum;i++){
                if(a[i]==0){
                    ans[tot++]=i;
                }
            }
            cout<<tot<<endl;
            for(int i=0;i<tot;i++){
                if(i==tot-1)cout<<ans[i]<<endl;
                else cout<<ans[i]<<' ';
            }
        }
    
    }

HDU:1261(JAVA)多重集的排列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

import java.math.BigInteger;
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner scn = new Scanner(System.in);
            int n;
            int a[]=new int [27];
            while(scn.hasNextInt()){
                n=scn.nextInt();
                if(n==0)break;
                int sum=0;
                for(int i=1;i<=n;i++){
                    a[i]=scn.nextInt();
                    sum+=a[i];
                }
                BigInteger ans=BigInteger.ONE;
                for(int i=1;i<=sum;i++){
                    ans=ans.multiply(BigInteger.valueOf(i));
                }
                BigInteger ansm=BigInteger.ONE;
                for(int i=1;i<=n;i++){
                    int x=1;
                    for(int j=1;j<=a[i];j++){
                        x*=j;
                    }
                    ansm=ansm.multiply(BigInteger.valueOf(x));
                }
                System.out.println(ans.divide(ansm));
            }
    
        }
    }

HDU：1028

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e4+10;
    int n;
    int a[maxn],b[maxn];
    void muhs(){
        memset(a,0,sizeof(a));
        for(int i=0;i<=n;i++)a[i]=1;
        for(int i=2;i<=n;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j<=n;j++){
                for(int k=0;k<=n&&j+k<=n;k+=i){
                    b[j+k]+=a[j];
                }
            }
            memcpy(a,b,sizeof(b));
        }
    }
    int main(){
        while(cin>>n){
            muhs();
            cout<<a[n]<<endl;
        }
    
    
        return 0;
    }

HDU：2069（二维母函数）控制了硬币的数量

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=310;
    int n;
    int a[maxn][105],b[maxn][105];
    int v[10]={
         1,5,10,25,50};
    void muhs(){
        memset(a,0,sizeof(a));
        for(int i=0;i<=100;i++)a[i][i]=1;
        for(int i=1;i<5;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j<=n;j++){
                for(int k=0;k+j<=n;k+=v[i]){
                    for(int kk=0;kk+k/v[i]<=100;kk++){
                        b[k+j][kk+k/v[i]]+=a[j][kk];
                    }
                }
            }
            for(int j=0;j<=n;j++){
                for(int k=0;k<=100;k++){
                    a[j][k]=b[j][k];
                    b[j][k]=0;
                }
            }
        }
    }
    
    
    int main(){
        while(cin>>n){
            muhs();
            int ans=0;
            for(int i=0;i<=100;i++)ans+=a[n][i];
            cout<<ans<<endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11382708.html

[https_blog.csdn.net_xiaofei_it_article_details_17042651]: https://blog.csdn.net/xiaofei_it/article/details/17042651
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/7a3f104d82ed45a08f06e650f46e6f9f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关用母函数解组合问题

1.引言母函数是解组合问题的工具，关于母函数的介绍参考百度百科：[http://baike.baidu.com/view/2415279.htm][h...

你的名字/ 2024年04月18日 02:45/ 0 赞/ 67 阅读

相关组合数学--母函数

模板：（转载：[https://blog.csdn.net/xiaofei\_it/article/details/17042651][https_blog.csdn.net_

约定不等于承诺〃/ 2023年06月03日 13:52/ 0 赞/ 29 阅读

相关 HDU 1521 排列组合（指数型母函数）

HDU 1521 排列组合（指数型母函数）：[http://acm.hdu.edu.cn/showproblem.php?pid=1521][http_acm.hdu.edu.

淩亂°似流年/ 2022年07月25日 15:57/ 0 赞/ 146 阅读

相关 HDU-1521 排列组合 (指数型母函数)

排列组合有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有”AB”,”BA”两种。 I

我不是女神ヾ/ 2022年06月09日 11:20/ 0 赞/ 135 阅读

相关母函数入门

母函数也叫生成函数，是组合数学中尤其是计数方面的一个重要理论和工具。母函数有普通型母函数和指数型母函数两种，其中普通型用的比较多。形式上说，普通型母函数用于解决多重集的组合问题

ゝ一纸荒年。/ 2022年06月09日 10:47/ 0 赞/ 246 阅读

相关母函数

int a[1001],b[1001]; int v[201],n1[201],n2[201]; / Function:

逃离我推掉我的手/ 2022年05月28日 12:57/ 0 赞/ 266 阅读

相关组合数学选择题

1.【题目】美团有个传统，就是公司各部门每月都要组织员工进行一次团建互动(team building，简称TB)，每个员工都可以带家属参加。活动内容出了吃喝玩之外，还要做一些互

梦里梦外;/ 2022年05月18日 08:27/ 0 赞/ 323 阅读

相关组合数学 (二): 排列组合

排列组合公式排列组合代码输出所有排列错位排列输出所有组合公式排列从

本是古典何须时尚/ 2022年02月21日 14:54/ 0 赞/ 396 阅读

相关组合数学 (三): 排列组合的数学逻辑

排列组合的数学逻辑前言排列圆排列项链排列组合 n 个相同的小球放到 m 个相同的盒子里

怼烎@/ 2022年02月14日 01:18/ 0 赞/ 706 阅读

相关母函数

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] 学了好长时间母函数了，一直没时间进行总结（忙于一些琐事），今天正好放一

冷不防/ 2022年01月15日 10:11/ 0 赞/ 275 阅读