定义 a[i][j]表示 j个球放到i个盒子里
考虑每次新加进来的盒子
这个盒子可以放k个球（k = 1 到 i-j+1）这有 C（j，k）种取法
剩下来的盒子的方案数 等于a[i-1][j-k],则根据乘法原理 这种情况下 共有C(j,k)*a[i-1][j-k]种方案
所以 a[i][j]= sum( C(j,k)*a[i-1][j-k] ) (k = 1 to i-j+1)
然后预处理一下C数组 直接递推就可以了
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=30;
LL c[N][N],a[N][N],n,r;//a[i][j]表示j个球放入i个盒子

int main(){
scanf("%lld%lld",&n,&r);
for(int i=0;i<=n;i++) c[i][0]=1LL;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
for(int i=1;i<=n;i++) a[1][i]=1LL;
for(int i=2;i<=r;i++)
for(int j=n;j>=i;j--)
for(int k=1;k<=j-i+1;k++) a[i][j]+=c[j][k]*a[i-1][j-k];
printf("%lld",a[r][n]);
return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    const ll csize=15;
    
    ll n,m;
    ll jc[csize+1];
    ll f[csize+1][csize+1];
    
    void main()
    {
        memset(jc,0,sizeof(jc));
        jc[0]=1;
        for (ll i=1;i<=csize;i++)
            jc[i]=jc[i-1]*i;
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for (ll i=1;i<=csize;i++)
            for (ll j=1;j<=i;j++)
                f[i][j]=f[i-1][j-1]+j*f[i-1][j];
        while (~scanf("%lld%lld",&n,&m))
            printf("%lld\n",f[n][m]*jc[m]);
    }
};

int main()
{
    dts::main();
}

推导方法：设f（ball，box）表示ball个异球放入box个异盒。
则第一个盒子可以放1个球：c（n，1）*f（ball-1，box-1）
或者第一个盒子可以放两个球：c（n,2）*f(ball-2,box-1)
or we can put three balls in the first box: c(n,3)*f(ball-3,box-1)
....................................
until we can put ball-(box-1) balls in the first box
although this method is a little difficult in realize,it's a good way to know the principles in this problem.

#include<iostream>
#include<string.h>
using namespace std;
long long int a[13][13];
int box, ball;
void init(){
int i, j;
a[0][0] = 1;
for (i = 1; i <= ball; i++){
for (j = 1; j <=box&&j<=i; j++){
long long int c = 1;
int k;
for (k = 1; k <= i+1-j; k++){
c *= (i + 1 - k);
c /= k;
a[i][j] += c*a[i - k][j - 1];
}
}
}
}
int main(){
//freopen("in.txt", "r", stdin);
memset(a, 0, sizeof(a));
cin >> ball>>box;
init();
cout << a[ball][box]<< endl;
return 0;
}

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,r,f[11][11]={1},ans=1;
int main()
{
scanf("%d%d",&n,&r);
for(int i=1;i<=r;i++)
ans*=i;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
f[i][j]=j*f[i-1][j]+f[i-1][j-1];
printf("%d",f[n][r]*ans);
return 0;
}

#include <stdio.h>
int c(int a, int b)
{
int i,ans=1;
for(i=0;i<b;i++) ans=ans*(a-i);
for(i=0;i<b;i++) ans=ans/(i+1);
return ans;
}
int func(int n,int r)
{
int i,k=n-r+1,ans=0;
if(r==1) return 1;
if (n==r)
{
ans=1;
for(i=1;i<=n;i++)
ans=ans*i;
return ans;
}
for(i=1;i<=k;i++)
{
ans=ans+c(n,i)*func(n-i,r-1);
}
return ans;
}

int main()
{
int n,r;
scanf("%d %d",&n,&r);

printf("%d",func(n,r));
return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=30;
LL c[N][N],a[N][N],n,r;//a[i][j]表示j个球放入i个盒子

int main(){
scanf("%lld%lld",&n,&r);
for(int i=0;i<=n;i++) c[i][0]=1LL;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
for(int i=1;i<=n;i++) a[1][i]=1LL;
for(int i=2;i<=r;i++)
for(int j=n;j>=i;j--)
for(int k=1;k<=j-i+1;k++) a[i][j]+=c[j][k]*a[i-1][j-k];
printf("%lld",a[r][n]);
return 0;
}

#include<cstdio>
#include<cstring>
using namespace std;

int f[15][15];

int main()
{
int n, k;
f[0][0] = 1;
scanf("%d%d", &n, &k);

for(int i=1; i<=n; i++)
for(int j=1; j<=k; j++)
f[i][j] = j * f[i-1][j] + f[i-1][j-1];
for(int i=1; i<=k; i++)
f[n][k] *= i;
printf("%d", f[n][k]);
return 0;
}
Stirling第二类 + 考虑不同盒子的排列

编译通过...

├ 测试数据 01：答案正确... (0ms, 580KB)

├ 测试数据 02：答案正确... (0ms, 580KB)

├ 测试数据 03：答案正确... (0ms, 580KB)

├ 测试数据 04：答案正确... (0ms, 580KB)

├ 测试数据 05：答案正确... (0ms, 580KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 580KB

终于知道为什么WA了，类型开integer，小了……

当n=10,r=10时，答案是3628800……

这题怎么没见打表的大神？

看了维基之后会做了，比较有意思

program p1210;

var n,r:integer;

procedure init;

begin

readln(n,r);

end;

function jc(r:integer):int64;

var i:integer;

begin

if r=1 then jc:=1

else for i:=2 to r do jc:=i*jc(i-1);

end;

function s(n,r:integer):int64;

begin

if (r=n) or (r=1) then s:=1

else s:=s(n-1,r-1)+r*s(n-1,r);

end;

begin

init;

writeln(jc(r)*s(n,r));

end.

太水了，不就是斯特林数嘛！

嫩KK；

程序就不贴了，太简单了~~~~~

strling*r！

var

n,r,sum,i:longint;

function s(n,r:longint):longint;

begin

if r>n then begin s:=0; exit end;

if (r=1)or(n=r)or((n=0)and(r=0)) then begin s:=1; exit end;

s:=s(n-1,r-1)+r*s(n-1,r);

end;

begin

readln(n,r);

sum:=s(n,r);

for i:=1 to r do

sum:=sum*i;

writeln(sum);

end.

f表示前i个球放在j个盒子的方案总数

f:=f+f*j

Ans:=f[n,r]*A(r,r)

{普通的第二类Strling不用这一步，这一步只是因为盒子也有序号。}

#include

using namespace std;

int sort(int n,int m)

{

if(m==1)return 1;

if(m==0)return 0;

if(m>n)return 0;

if(m==n)return 1;

return sort(n-1,m-1)+m*sort(n-1,m);

}

int main()

{

int s,n,m,sum=1,i;

cin>>n>>m;

s=sort(n,m);

for(i=1;i

Accepted 有效得分：100 有效耗时：0ms

第一次为什么会runing，数组20......谁能解释下....

f:=(f+f)*j

f[1,1]~f[n,1]=1;

F(n,r)=r*(F(n-1,r-1)+F(n-1,r));

longint秒杀（注意边界条件）

好长啊 .. 而且是错的 ..

Program ex;var s:array[0..10,0..10] of longint ; n,k,i,j:longint ;function e2(q:longint):longint ;var i,x:longint;begin x := 2 ; for i := 2 to q do x := x * 2 ;end ;function c(n,r:longint):longint ;var i,x:longint ; function jc(x:longint):longint ; var i,s:longint ; begin s := 1 ; for i := 1 to x do s := s * i ; exit(s) ; end ;begin x := jc(n) div (jc(r) * jc(n-r)) ; exit(x) ;end ;function solve(n,k:longint) : longint ;begin if s[n,k] 0 then exit(s[n,k]) else solve := solve(n-1,k-1) + k * solve(n-1,k) ;end ;BEGIN read(n,k) ; fillchar(s,sizeof(s),0) ; for i := 1 to n do begin s := 1 ; s := e2(i-1) - 1 ; s := 1 ; s := c(i,2) ; end ; writeln(solve(n,k) * k) ;END .

公式推出来了,不过没想到要*r!

感谢大牛们题解,深受启发.

#include

using namespace std;

int main(){

int n,r;

int f[20][100]={0};

cin>>n>>r;

for (int i=1 ; i