精华内容
下载资源
问答
  • 集合划分问题 给定正整数n,mn,mn,m,计算出nnn个元素集合{1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n}可以划分为多少个不同由mmm个非空子集合组成集合。 (1)解题原理 ​ 根据题目所给划分规则,设s[n][m]s[n][m...

    集合划分问题

    给定正整数n,mn,m,计算出nn个元素的集合{1,2,,n}\{1,2,\cdots,n\}可以划分为多少个不同的由mm个非空子集合组成的集合。

    (1)解题原理

    ​ 根据题目所给的划分规则,设s[n][m]s[n][m]nn个元素划分为mm个非空子集的集合的个数,则我们从两方面来考虑这个数量的由来:

    ​ (1)固定n1n-1个元素,考虑最后一个元素的单独划分:考虑s[n1][m1]s[n-1][m-1],其表示将n1n-1个元素划分为m1m-1个非空集合,则我们只需要将剩下的那一个元素单独作为一个集合即可得到mm个非空集合的nn个元素的划分;

    ​ (2)固定mm种划分,考虑最后一个元素的加入情况:考虑s[n1][m]s[n-1][m],其表示将n1n-1个元素划分为mm个非空集合,则我们需要考虑剩下的那个元素进入哪一个集合,显然共有mm种情况

    ​ 因此,我们可以得到下面的计算式:
    s[n][m]=s[n1][m1]+ms[n1][m] s[n][m]=s[n-1][m-1]+m*s[n-1][m]
    ​ 其中,有退化结果:
    s[0][j]=0,s[i][1]=1,s[i][i]=1,s[i][j]=0(i<j) s[0][j]=0,s[i][1]=1,s[i][i]=1,s[i][j]=0(i<j)
    ​ 从而我们可以使用分治递归算法或打表记录的方法得到最后划分情况。

    (2)解题步骤

    ​ 若使用打表法:

    ​ Ⅰ.初始化ss数组

    ​ Ⅱ.双重forfor循环遍历,填充对应位置处的s[i][j]s[i][j]的值

    ​ Ⅲ.输出结果至输出文件,并记录程序运行时间

    ​ 分治递归法:

    ​ Ⅰ.设置递归基:if(n==0||n<m)return 0;if(m==1||m==n)return 1;

    ​ Ⅱ.递归计算s[i][j]s[i][j],即return m*s[n-1][m]+s[n-1][m-1]

    ​ Ⅲ.输出结果至输出文件,并记录程序运行时间

    关键代码

    unsigned long long f(int n,int m){		//分治递归法
        if(m==0||m>n)return 0;
        if(m==1||m==n)return 1;
        return m*f(n-1,m)+f(n-1,m-1);
    }
    
    for(int i=0;i<=n;i++)					//初始化
        for(int j=0;j<=m;j++){
            a[i][j]=0;
            if(i==j)a[i][j]=1;
        }	
    for(int i=1;i<=n;i++)					//打表记录法
        for(int j=1;j<=m;j++){
            if(i>=j)
                a[i][j]=j*a[i-1][j]+a[i-1][j-1];
            else a[i][j]=0;
        }
    

    测试结果

    在这里插入图片描述

    (3)复杂度分析

    ​ 打表记录法:由关键代码的双重forfor循环,可得其时间复杂度为O(nm)O(nm)

    ​ 分治递归法:其时间复杂函数T(n,m)T(n,m)存在一个下界Ω(min{2nm,2m1})\Omega(min\{2^{n-m},2^{m-1}\}),存在一个上界O(2n1)O(2^{n-1})即分支递归法解集合划分问题的时间复杂度为指数级。

    分治递归法的时间复杂度证明

    由计算式:s[n][m]=s[n1][m1]+ms[n1][m]s[n][m]=s[n-1][m-1]+m*s[n-1][m],得到:
    T(n,m)=T(n1m1)+T(n1,m) T(n,m)=T(n-1,m-1)+T(n-1,m)

    下界

    ​ 其解可视作一棵二叉树,每个状态都有两种不同的子状态,考虑其下界,即一直走左子节点或右子节点,即有:

    a.一直走左子节点

    T(n,m)T(n1,m1)+T(n1,m1)=2T(n1,m1) T(n,m)\approx{T(n-1,m-1)+T(n-1,m-1)}=2T(n-1,m-1)

    ​ 由题有n>mn>m,利用乘法消项:
    T(n,m)=2T(n1,m1)2T(n1,m1)=22T(n2,m2)2m2T(nm+2,2)=2m1T(nm+1,1) T(n,m)=2T(n-1,m-1)\\2T(n-1,m-1)=2^2{T(n-2,m-2)}\\\cdots\\\cdots\\{2^{m-2}T(n-m+2,2)=2^{m-1}T(n-m+1,1)}
    ​ 由之前列出的退化结果,其出口为s[i][1]=1s[i][1]=1于是可以得到:
    T(n,m)=2m1T(nm+1,1)=2m1 T(n,m)=2^{m-1}T(n-m+1,1)=2^{m-1}

    b.b.一直走右子节点

    T(n,m)T(n1,m)+T(n1,m)=2T(n1,m) T(n,m)\approx{T(n-1,m)+T(n-1,m)}=2T(n-1,m)

    ​ 同理有n>mn>m,利用乘法消项:
    T(n,m)=2T(n1,m)2T(n1,m)=22T(n2,m)2n(m+1)T(m+1,m)=2nmT(m,m) T(n,m)=2T(n-1,m)\\2T(n-1,m)=2^2{T(n-2,m)}\\\cdots\\\cdots\\{2^{n-(m+1)}T(m+1,m)=2^{n-m}T(m,m)}
    ​ 由之前的退化结果,可以得此时的出口为s[i][i]=1s[i][i]=1于是我们可以得到:
    T(n,m)=2nmT(m,m)=2nm T(n,m)=2^{n-m}T(m,m)=2^{n-m}
    ​ 因此我们得到此方法的下界为:
    T(n,m)=Ω(min{2nm,2m1}) T(n,m)=\Omega(min\{2^{n-m},2^{m-1}\})

    上界

    ​ 考虑解在二叉树左右子节点反复横跳的情况,不难得出极端情况为:一次左,一次右,因此我们可以将之前计算的单走某一支的情况相乘即表示所有可能的情况。

    ​ 不难得出,其上界为:
    T(n,m)=2nm×2m1=O(2n1) T(n,m)=2^{n-m}\times2^{m-1}=O(2^{n-1})

    展开全文
  • 集合划分问题(一)

    2020-05-30 02:55:52
    集合划分问题(一) Input 多组输入数据,每组数据1行,表示元素个数n. Output 对于每组数据,输出一行一个数,表示不同的非空子集的个数。 Sample Input 24 Sample Output 215 `` import java.io.; / 分析: ...

    集合划分问题(一)

    Input

    多组输入数据,每组数据1行,表示元素个数n.
    Output

    对于每组数据,输出一行一个数,表示不同的非空子集的个数。
    Sample Input

    24
    Sample Output

    215

    ``
    import java.io.;
    /

    • 分析:

    • 考虑3个元素的集合,可划分为

    • ① 1个子集的集合:{{1,2,3}}

    • ② 2个子集的集合:{{1,2},{3}},{{1,3},{2}},{{2,3},{1}}

    • ③ 3个子集的集合:{{1},{2},{3}}

    • ∴F(3,1)=1;F(3,2)=3;F(3,3)=1;

    • 如果要求F(4,2)该怎么办呢?

    • A.往①里添一个元素{4},得到{{1,2,3},{4}}

    • B.往②里的任意一个子集添一个4,得到

    • {{1,2,4},{3}},{{1,2},{3,4}},

    • {{1,3,4},{2}},{{1,3},{2,4}},

    • {{2,3,4},{1}},{{2,3},{1,4}}

    • 那么显然F(4,2)=F(3,1)+2F(3,2)=1+23=7

    • 进行推广,可以归纳出递推公式:F(n,m)=F(n-1,m-1)+m*F(n-1,m)

    • */
      class lab1_2_5{
      public static void main(String[] args) throws IOException{
      File outFile = new File(“F://input1.2.5.txt”);//要现在F盘建文件
      BufferedReader br = new BufferedReader(new FileReader(outFile));
      String str = br.readLine();//读取文件的数据
      int n = Integer.parseInt(str);
      String data = aggregateAmount(n)+"";
      File inFile = new File(“F://output1.2.5.txt”);
      Writer out = new FileWriter(inFile);
      out.write(data);
      out.close();

      }
      //计算所有子集合的数量。调用递归公式
      public static int aggregateAmount(int n){
      int sum = 0;
      for(int i = 1;i <= n;i++){
      sum += subsetAmount(n,i);
      }
      return sum;
      }
      public static int subsetAmount(int n,int m){//用递归求子集合的数目
      if(n < m || n == 0 ||m == 0)
      return 0;
      else if(n == 1)
      return 1;
      else
      return subsetAmount(n - 1,m - 1) + msubsetAmount(n-1,m);
      }
      }
      /

    • 心得:

    • 这道题用到了递归,我是先从n = 1开始算,一直算到n = 4 答案差不多就出来了

    • */
      ``

    展开全文
  • 题意 一个有\(n\)个元素的集合,将其分为任意个非空子集,...设\(f_n\)表示用\(n\)个元素组成的集合的个数,显然\(f_n=1\)。设\(F(x)\)为\(f\)的指数型生成函数,那么\(F(x)=\sum_{i=1}\frac{x^i}{i!}\),\(F^i(x)\...

    题意

    一个有\(n\)个元素的集合,将其分为任意个非空子集,求方案数。集合之间是无序的,\(\{\{1,2\},\{3\}\}=\{\{3\},\{1,2\}\}\)


    \(f_n\)表示用\(n\)个元素组成的集合的个数,显然\(f_n=1\)。设\(F(x)\)\(f\)的指数型生成函数,那么\(F(x)=\sum_{i=1}\frac{x^i}{i!}\)\(F^i(x)\)的第\(n\)位就是\(i\)个元素个数之和为\(n\)的集合组合在一起的方案数。

    \(g_i\)\(n=i\)时的答案,再设\(G(x)\)\(g\)的指数型生成函数。枚举划分的集合个数:

    \[ G(x)=\sum_{i=0}\frac{F^i(x)}{i!} \]

    显然\(F(x)=e^x-1\),那么\(G(x)=e^{e^x-1}\)\(G(x)\)\(i\)项乘\(i!\)就是\(g_i\)。多项式\(exp\)即可。

    #include<bits/stdc++.h>
    #define rg register
    #define il inline
    #define cn const
    #define gc getchar()
    #define fp(i,a,b) for(rg int i=(a),ed=(b);i<=ed;++i)
    #define fb(i,a,b) for(rg int i=(a),ed=(b);i>=ed;--i)
    using namespace std;
    typedef cn int cint;
    il int rd(){
       rg int x(0),f(1); rg char c(gc);
       while(c<'0'||'9'<c){ if(c=='-') f=-1; c=gc; }
       while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc;
       return x*f;
    }
    cint inf=0x3f3f3f3f,maxn=1000010,mod=998244353;
    
    int T,n=100000,inv[maxn],fac[maxn],ifac[maxn];
    int a[maxn],f[maxn],g[maxn],A[maxn],B[maxn];
    int lim=1,l,rev,r[maxn];
    
    il int fpow(int a,int b,int ans=1){
        for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
        return ans;
    }
    il int finv(cint &n){return fpow(n,mod-2);}
    cint G=3,invG=finv(G);
    
    il void ntt(int *a,cint &f){
        fp(i,0,lim-1)if(i<r[i])swap(a[i],a[r[i]]);
        for(rg int md=1;md<lim;md<<=1){
            rg int len=md<<1,Gn=fpow(f?G:invG,(mod-1)/len);
            for(rg int l=0;l<lim;l+=len){
                rg int Pow=1;
                for(rg int nw=0;nw<md;++nw,Pow=1ll*Pow*Gn%mod){
                    rg int x=a[l+nw],y=1ll*Pow*a[l+nw+md]%mod;
                    a[l+nw]=(x+y)%mod,a[l+nw+md]=(x-y+mod)%mod;
                }
            }
        }
    }
    
    void get_inv(int *a,int *b,int n){
        if(n==1){b[0]=finv(a[0]);return;}
        get_inv(a,b,n>>1);
        fp(i,0,n)B[i]=a[i];
        lim=1,l=0; while(lim<=n<<1)lim<<=1,++l; rev=finv(lim);
        fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        ntt(B,1),ntt(b,1);
        fp(i,0,lim)b[i]=1ll*b[i]*((2-1ll*B[i]*b[i]%mod+mod)%mod)%mod; ntt(b,0);
        fp(i,0,n)b[i]=1ll*b[i]*rev%mod; fp(i,n+1,lim)b[i]=0;
        fp(i,0,lim)B[i]=0;
    }
    
    il void get_ln(int *a,int *b,int n){
        fp(i,1,n)A[i-1]=1ll*a[i]*i%mod; get_inv(a,b,n);
        lim=1,l=0; while(lim<=n<<1)lim<<=1,++l; rev=finv(lim);
        fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        ntt(A,1),ntt(b,1);
        fp(i,0,lim)b[i]=1ll*b[i]*A[i]%mod; ntt(b,0);
        fp(i,0,n)b[i]=1ll*b[i]*rev%mod; fp(i,n+1,lim)b[i]=0;
        fp(i,0,lim)A[i]=0;
        fb(i,n,1)b[i]=1ll*b[i-1]*inv[i]%mod; b[0]=0;
    }
    
    void get_exp(int *a,int *f,int n){
        if(n==1){f[0]=1;return;}
        get_exp(a,f,n>>1),get_ln(f,g,n);
        g[0]=(1-g[0]+a[0]+mod)%mod; fp(i,1,n)g[i]=(a[i]-g[i]+mod)%mod;
        lim=1,l=0; while(lim<=n<<1)lim<<=1,++l; rev=finv(lim);
        fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        ntt(f,1),ntt(g,1);
        fp(i,0,lim)f[i]=1ll*f[i]*g[i]%mod; ntt(f,0);
        fp(i,0,n)f[i]=1ll*f[i]*rev%mod; fp(i,n+1,lim)f[i]=0;
        fp(i,0,lim)g[i]=0;
    }
    
    int main(){
        fac[0]=1; fp(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
        inv[1]=1; fp(i,2,n)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        ifac[0]=1; fp(i,1,n)ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
        
        fp(i,1,n)a[i]=ifac[i];
        while(lim<=n)lim<<=1; get_exp(a,f,lim);
        
        T=rd();
        while(T--)n=rd(),printf("%lld\n",1ll*f[n]*fac[n]%mod);
        return 0;
    }
    展开全文
  • 整数集合划分 简单贪心 题目要求: 使得两个集合的个数尽量的小,然后在那个基础上使得两个集合的差最大 集合个数尽量的小 >> 不是 0 就是 1 ( 偶数 or 奇数 差最大 >> 一个将所有最小的 n / 2 个数...

    AcWing:1603. 整数集合划分

    在这里插入图片描述

    简单贪心

    题目要求: 使得两个集合的个数尽量的小,然后在那个基础上使得两个集合的差最大

    集合个数尽量的小 >> 不是 0 就是 1 ( 偶数 or 奇数

    差最大 >> 一个将所有最小的 n / 2 个数包揽, 另一个将剩余的最大的数包揽, 相减即可



    AC Code

    import java.util.*;
    import static java.lang.System.out;
    
    public class Main{
        
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) arr[i] = in.nextInt();
            Arrays.sort(arr);
            int k = n % 2;
            int pre = 0, suf = 0;
            
            for(int i = 0; i < n; i++) {
                if(i < n / 2) pre += arr[i];
                else suf += arr[i];
            }
            
            out.println(k + " " + (suf - pre));
        }
        
    }
    



    展开全文
  • 题目思路:利用并查集对相互认识人进行集合的划分划分完毕后进行遍历,如果发现一个点根节点是本身,证明找到一个集合,统计集合数便是答案了。 #include<cstdio> #include<cstdlib&g...
  • 题目描述 ...要求 Ci≤Ci+1C_i\le C_{i+1}Ci​≤Ci+1​,且选择的 AAA 的个数恰为 nnn 个,问方案数,方案不同当且仅当某个位置的选择不同。 n≤5∗104,mod  998244353n\le 5*10^4,\mod 99824435
  • 5292. 划分数组为连续数字的集合 题解: 模拟题(不涉及算法,就是按题目意思编写代码的题就叫模拟题),说实话,我真是个废物,连模拟题都想不好,真的被自己菜哭了。 思路:用map存放<数字,该数字的个数>...
  • 文章目录前言如何证明八数码问题无解 前言 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8...每个数字前面比它大的数字的个数的和称为这个状态的逆序数。 现在来看两个例子中,除去数字0
  • 整数划分

    2016-08-12 20:53:37
    这里我们记n的m划分的个数为f(n,m)。 例如,当n=4时,有5个划分,即 {4},{3+1},{2,2},{2,1,1},{1,1,1,1} 注意: {3,1} 和{1,3} 被认为是同一个划分。 根据n和m的关系,考虑一下几种情况: (一)当n...
  • 在上一篇博客中,我介绍了等价类划分法的... ①在输入条件规定了取值范围或值的个数的情况下,则可以确立一个有效等价类和两个无效等价类。  ②在输入条件规定了输入值的集合或者规定了“必须如何”的条件的情况...
  • 在此过程中经常需要判断该元素是否属于某个集合,或查询该集合中元素的个数。适用于解决这类问题的数据结构类型称为并查集。 题目1:.547. 朋友圈 题目2:990. 等式方程的可满足性 2.并查集原理 通过数组下标标识...
  • 划分关系 姑且这么叫着 设满足性质 AAA 的集合为 SAS_ASA​,每个元素有标号 如果 SBS_BSB​ 是由若干个 SAS_ASA​ 组成的一个大集合 设 aia_iai​ 表示大小为 iii 的 SAS_ASA​ 的个数 设 bib_ibi​ 表示大小为 iii...
  •  给定一个集合S和数n,从集合S中取出两个不同的数a,b满足a+b=n的总...是否有可能把全体非负整数划分为A、B两个集合,使得对于任意一个n,集合A和集合B中关于n的互补数对的个数都相同? 答案是肯定的。此处,神奇的
  • 整数划分(C语言实现)

    千次阅读 2017-05-05 11:04:22
    指把一个正整数n写成多个大于等于1且小于等于其本身的整数的和,则其中各加数所构成的集合为n的一个划分。这是一个典型的递归算法。 所谓整数划分,是指把一个正整数n写成为 ...这里我们记n的m划分的个数
  • 有n个无区别的物品,将它们划分为不超过m组,求出划分方法数模M的余数。 题目我就不废话了,照着书看。...当然了球的个数肯定不为负数 ,也就是&gt;=0。 现在根据题目来还原,m个袋子代表m个划分,有的袋子为0...
  •   从给定的集合中求互质四元组的个数。   解题思路:先求解非互质四元组的个数,在总体四元组个数减去这个数目。求非互质四元组即求公因数大于1的四元组数目,因此,使用公因数d把集合中的元素划分成不同的子集...
  • 含义:将输入(输出)划分为若干个子集合,从划分的集合中选区代表的数据进行测试,如果选取的数据测试没有问题,就认为未被选取的数据测试效果是等价的原则: (1)如果输入的是一个取值范围或者值的个数,则划分...
  • 在输入条件规定了取值范围或值的个数的情况下,可以确立一个有效等价类和两个无效等价类。 输入条件规定了输入值的集合或者规定了“必须如何”的条件的情况下,可确立一个有效等价类和一个无效等价类。 在输入条件是...
  • 菜鸟系列——划分

    2015-06-18 00:36:07
    做回菜鸟,老老实实重新学起: 划分树 数据结构; 求k大值及左右和模版: #define N 123456 int sorted[N]={0}; //对原集合中元素排序后的... //记录元素所在区间当前位置前的元素进入到左子树的个数 int lnum, rnum;
  • 如果规定了输入数据的个数,则类似地可以划分出一个有效等价类和两个无效等价类 3,按数值集合划分 如果输入数据的一组值,且程序对不同输入值做不同处理,则每一个允许的输入值都是一个有效等价类,并有一个...
  • 首先可以枚举子集$3^n$转移,优化是额外记录每个集合选取的个数,然后按照选取个数从小到大转移。转移的时候先FWT成“点值”转移完了IFWT回去乘逆元 沙茶博主也不知道为什么这样就是对的,放个没看懂的yww大佬的...
  • [WC2018]州区划分

    2018-08-04 19:36:00
    Descripiton Solution 有一个比较显然的子集 \(DP\) 设 \(f[s]\) 表示集合状态为 \(s\) 的所有划分方案的满意度之和 \(f[s]=\sum_{t∈s}f[t]*...由于这个题元素不能有交 , 所以我们需要多定义一维表示 \(1\) 的个数...
  • 算法概论上机集合

    2019-07-08 23:47:03
    实验一 实验目的与要求:理解分治法的基本思想和设计方法。...A[j],则称A[i]与A[j]构成了一个逆序对,设计算法求数列A中逆序对的个数. 3. 引入逆序计数问题作为考察两个序列有多大差别的一个好的度量指标。但是...
  • 等价类划分法实例

    2010-10-25 11:51:50
    1、在输入条件规定了取值范围或值的个数的情况下,则可以确立一个有效等价类(在范围之内的等价类)和两个无效等价类(有效范围的两侧)。 2、在输入条件规定了输入值的集合或者规定了“必须如何”的条件的情况下,则...
  • 斯特灵数:把nn个数划分为恰好kk个非空集合的个数,记为S(n,k)S(n, k)。且有:S(n,1)=S(n,n)=1S(n, 1) = S(n, n) = 1。 有递推关系式:S(n+1,k)=S(n,k−1)+kS(n,k−1)S(n + 1, k) = S(n, k - 1) + kS(n, k - 1) ...
  • 【黑盒测试用例设计】测试方法之等价类划分法 原理:把输入或输出数据划分为有效和无效等价类,从每个等价类中选取具有代表性的数据进行测试。...(1+2)在输入条件规定了取值范围或值的个数的情况下
  • 思路:动态规划,dp[i]dp[i]dp[i]表示以i位置的数为结尾中形成等差数列的个数集合。则每次如果以A[i]、A[i−1]、A[i−2]A[i]、A[i-1]、A[i-2]A[i]、A[i−1]、A[i−2]形成一个等差数列,则这个A[i]有可能由和之前i-...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 166
精华内容 66
关键字:

集合划分的个数