题目描述

@发源于 小朋友最近特别喜欢球。有一天他脑子抽了,从口袋里拿出了N个不同的球,想把它们放到M个相同的盒子里,并且要求每个盒子中至少要有一个球,他好奇有几种放法,于是尝试编程实现,但由于他天天不好好学习,只会上B站看游泳教练,于是他向你求助。

输入输出格式

输入格式:

多组数据,每行两个数N,M。

输出格式:

每组数据一行,表示方案数。

输入输出样例

输入样例#1:

4 2
1 1
输出样例#1:

7
1

说明

【样例解释】

N=4,M=2

1,2 3 4

2,1 3 4

3,1 2 4

4,1 2 3

1 2,3 4

1 3,2 4

1 4,2 3

对于20%的数据,满足1≤N,M≤10;

对于100%的数据,满足1≤N,M≤100,数据组数≤10。

题解:高精+第二类Stirling数

递推公式s[i][j]=s[i-1][j]*j+s[i-1][j-1]

s[i][j]的一个组合学解释是:将i个物体划分成j个非空的不可辨别的(可以理解为盒子没有编号)集合的方法数。

考虑最后一个物品的去向,要么单独一个盒子,要么随便选一个盒子。

初始化:s[i][1]=s[i][i]=1,m<n||n==0 return 0;

ps:Candy?的高精模板太好看了。%

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define B 10
using namespace std;
LL m,n;
struct Big{
int a[], n;
int& operator [](int x) {return a[x];}
Big():n() {memset(a, , sizeof(a));}
void ini(int x) {a[]=x; n=;}
}t[][]; Big operator *(Big a, int b) {
int g=;
for(int i=; i<=a.n; i++)
g += a[i]*b, a[i] = g%, g/=;
if(g) a[++a.n] = g;
return a;
} Big operator *(Big a, Big b) {
Big c;
for(int i=; i<=a.n; i++) {
int g=;
for(int j=; j<=b.n; j++)
g += c[i+j-]+a[i]*b[j], c[i+j-] = g%, g/=;
c[i+b.n] = g;
}
c.n = a.n + b.n;
while(c.n> && c[c.n]==) c.n--;
return c;
} Big operator +(Big a, Big b) {
int g=, n=max(a.n, b.n);
for(int i=; i<=n; i++) {
g += i<=a.n ? a[i] : ;
g += i<=b.n ? b[i] : ;
a[i] = g%, g/=;
}
a.n = n;
if(g) a[++a.n] = g;
return a;
} Big operator -(Big a, Big b) {
for(int i=; i<=b.n; i++) {
if(a[i]<b[i]) a[i]+=, a[i+]--;
a[i] -= b[i];
}
int p=b.n+;
while(a[p]<) a[p]+=, a[++p]--;
while(a.n> && a[a.n]==) a.n--;
return a;
} void Print(Big &a) {
printf("%d", a[a.n]);
for(int i=a.n-; i>=; i--) printf("%d", a[i]);
} int main(){
for(int i=;i<=;i++){
t[i][].a[]=;t[i][i].a[]=t[i][].a[]=;
}
for(int i=;i<=;i++)
for(int j=;j<=i-;j++)
t[i][j]=t[i-][j-]+t[i-][j]*j;
while(scanf("%lld%lld",&m,&n)!=EOF){
if(n==||n>m){printf("0\n");continue;}
Print(t[m][n]);
printf("\n");
}
return ;
}
05-15 22:51