【NOIP2017提高A组模拟9.17】组合数问题

题目

Description

定义＂组合数＂S(n,m)代表将n 个不同的元素拆分成m 个非空集合的方案数．

举个例子，将{1,2,3}拆分成2 个集合有({1},{2,3}),({2},{1,3}),({3},{1,2})三种拆分方法．

小猫想知道，如果给定n,m 和k,对于所有的0<=i<=n,0<=j<=min(i,m),有多少对(i,j),满足S(i,j)是k 的倍数．

注意，0 也是k 的倍数,S(0,0)=1,对于i>=1,S(i,0)=0．

Input

从problem.in 种读入数据第一行有两个整数t,k,t 代表该测试点总共有多少组测试数据.接下来t 行,每行两个整数n,m.

Output

输出到文件problem.out 中t 行,每行一个整数代表所有的0<=i<=n,0<=j<=min(i,m),有多少对(i,j),满足S(i,j)是k 的倍数.

Sample Input

输入1：

1 2

3 3

输入2：

2 5

4 5

6 7

Sample Output

输出1：

3

样例说明1：S(1,0),S(2,0),S(3,0)均是2 的倍数

输出2：

4

12

Data Constraint

对于20%的数据,满足n,m<=7,k<=5

对于60%的数据,满足n,m<=100,k<=10

对于每个子任务,都有50%的数据满足t=1

对于100%的数据,满足1<=n<=2000,1<=m<=2000,2<=k<=21,1<=t<=10000

题解

第二类斯特林数

公式：

\(S(i,j)=S(i-1,j-1)+j*S(i-1,j)\)

证明

当前这个元素新开一个集合，\(S(i-1,j-1)\)
当前这个元素进入一个原本存在的集合 \(j*S(i-1,j-1)\)

根据加法定理，两者相加就是答案

预处理的同时\(\%k\)

然后用二维前缀和统计0的个数

Code

#include<cstdio>

#include<iostream>

#define ull unsigned long long

using namespace std;

int t,k,k1,n,m,c[2001][2001],s[2001][2001];

int read()

{

	int res=0;char ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();

	return res;

}

int main()

{

	freopen("problem.in","r",stdin);

	freopen("problem.out","w",stdout);

	t=read();k=read();

	c[1][1]=c[0][0]=1;

	for (int i=2;i<=2000;++i)

		for (int j=1;j<=min(2000,i);++j)

			c[i][j]=(c[i-1][j-1]%k+j*c[i-1][j]%k)%k;

	for (int i=0;i<=2000;++i)

		for (int j=0;j<=i;++j)

			if (c[i][j]==0) s[i][j]=1;

	for (int i=1;i<=2000;++i)

		s[i][0]+=s[i-1][0],s[0][i]+=s[0][i-1];

	for (int i=1;i<=2000;++i)

		for(int j=1;j<=2000;++j)

			s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];

	while (t--)

	{

		n=read();m=read();

		printf("%d\n",s[n][m]);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

【NOIP2017提高A组模拟9.17】组合数问题

【NOIP2017提高A组模拟9.17】组合数问题

题目

Description

Input

Output

Sample Input

Sample Output

Data Constraint

题解

Code

最新文章

热门文章