P1287 盒子和球

基本功计数

题目叙述

现有r个互不相同的盒子和n个互不相同之球,要拿即时n个球放入r个盒子中,且未允有空盒子。问有稍许种方法?

比如说:有2个不等之盒子(分别编也1号和2号)和3只不同之球体(分别编为1、2、3声泪俱下),则生6栽不同之措施:

365bet体育投注 1

盒子和球

默认以下盒子为m 球为n

  1. 盒子不同 球相同
    • 莫能够也空 直接插板->C(n-1,m-1)
    • 得生出空 加入m个球使得变为上面问题
  2. 盒子相同 球不同
    • 非克来空 相当给划分集合 方案不同当且仅当有一个会师的元素不同
      那么尽管是老二类斯特林数
    • 可产生空 则枚举空的数量(无序)
  3. 盒子相同 球也同样
    • 马上即是独反复的分割

<span id=”skip”>数之细分 </span>

频是如出一辙看似集合无序球也不管别之题目

  1. n划分成k个数(f[n][k])
    • 就是k个
      • 使得末尾结果每个岗位都>=2
        则先行提出k个来放置每一个位置f[n-k][k]
      • 发啊1的位置 则保证它存在f[n-1][k-1]
    • 不超过k个(可以有0)
      • 上述第二种变为f[n][k-1] 就相当给放了个0堆积
  2. n划分成不大于k的数f[n][k]
    • 得生重
      • 每个数都<k f[n][k-1]
      • 有数为k f[n-m][m]
    • 每个数不同
      • 有数为k 使得前的高频不能够吧k -> f[n-m][m-1]

<span id=”jump”>####次类斯特林数</span>

n个发距离元素划分为m个无序聚集

  1. 求法

    • 递推式 (n^2)
      • 第i独因素放一个初的汇 s[i-1][j-1]
      • 第i只因素放入已发出集 s[i-1][j]*j
  2. 通项式求一行(FFT -> nlogn)
    [图形上传失败…(image-7439a9-1516201501882)]

  3. 要记的采用
    易下降幂与当幂 [图片及传失败…(image-bdb879-1516201501883)]
    n的k次下降幂是n(n-1)(n-2)(n-k-1)
    出只稍性 n(k+1)=n(k)(n-k)
    那么实际上 i^k 就是 sigma(S(k,j)
    j!*C(i,j))后面那无异垛便是跌幂

输入输出格式

输入格式:

 

点滴独整数,n和r,中间用空格分隔。(0≤n, r≤10)

 

输出格式: 

徒一行,一个整数(保证在长整型范围外)。表示n个球放入r个盒子的道。

 

错排

每个岗位都非是原来的多次的方案往往
少种植递推形式
f[i]=(i-1)(f[i-1]+f[i-2]) f[i]=f[i-1]i(-1)^i
同种非递推(也是O(n)不知晓出啊含义的样式) f[i]=sum{(-1)^i
n!/i!}

输入输出样例

输入样例#1: 复制

3 2

出口样例#1: 复制

6

string数

事态一样:n个相同盒子,m个不同小球,小球放入盒子,不容许盒子为空

直白第二像样stir满足第二像样stirling数(斯特林数);

莫打听的:http://baike.baidu.com/link?url=EPcGYyqDKzay4fVUasVpBI5tNS-Jqx6XukSIyIsXOUWy0z5HUtlDVDqY4UgXthNY8fkLqlolW6CGlM5c48OmE8IpjQ14I_4l_MdxJYI8F-G7emNboerFx_9ouqsg4DDM

f[i,j]否眼前i个稍圆球放入前j个盒子,且盒子无空的方案总数:

递推式:

解析如下:

(1)如果n个因素结合了m-1独集聚,那么第n+1个要素单独做一个会合。方案往往
S(n,m-1);

(2)如果n个要素就成了m个集合,将第n+1个元素插入到任意一个聚集。方案数
m*S(n,m) 。

归纳两种情景得:f[i,j]:=f[i-1,j]*j+f[i-1,j-1];

f[i,0]:=0^n;

f[1,1]:=1; f[i,i]:=1;
f[n,2]:=2^(n-1)-1; f[n,n-1]:=C(n,2);
f[n,m]=0;(m>n);ling数,求f[n,m]即可

情二:n个不同盒子,m个不同的小球,小球放入盒子,不容许盒子有空。

第二类stirling的变形,

结果为f[n,m]*m!

此题为情二

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,c[20][20]={1};
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int jie(int a)
{
    int res=1;
    for(int i=1;i<=a;i++)
     res*=i;
    return res;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
         c[i][j]=j*c[i-1][j]+c[i-1][j-1];
    }
    printf("%lld",1ll*c[n][m]*jie(m));
    return 0;
}

 

 

 

相关文章

网站地图xml地图