1120: 划分数
Time Limit: 8 Sec Memory Limit: 128 MB
Submit: 6 Solved: 3
[Submit][Status][Web Board]
Description
有n个无区别的物品，将它们划分成不超过m组，求出划分方法数模M的余数。
限制条件
1 <= m <= n <= 1000
2 <= M <= 10000
Input
每组测试数据输入一行n, m, M。
Output
输出划分数模M的余数。
Sample Input
42 468 6335
Sample Output
2494
HINT
组合数学
Source
可以将问题转变成x1+x2+x3+x4+x5+x6+.....xk+.....xm=n； <=xk;
这类问题一般有这样的限制:每个数的最大值,最小值,每个数是否可以相同.
相当于求不定方程x的非负整数解,但是n等于4时1 2和1 1根据题意，物品是相同的，所以这两种是一样的，
所以不能用校赛那道球放盒子的那种方式，
（考虑第i个盒子，放k个，d[i][j]+=d[i-][j-k];<=k<=m),
从整体进行考虑，对于每一个减去1，由于最小数可能为0，所以有两种情况，一种是最小数为0，一种是最小数为1，
d[m][n]=d[m][n-t]+d[m-][n],最小数为1，减去一，最小数为0，直接去掉0。，初始化d[][]=,
这种方式为什么可以去重呢？
当有多个最小值为0时，由于去0时没有考虑去掉的是哪一个,所以去0操作跟位置没有关系。
(最小数为0，可能有多个，假设是k个，去k次，跟位置无关，去k次就可去完)
假设这个数是0,0,2,不考虑位置的去0,所以可以去重.
将n个数划分为m个不同的正整数解，且最大值小于n
f1[t][x]=f[t][x-t]+f[t-][x-t]-f[t-][x-(n+)]
将n个数划分为m个不同的正整数解
f2[t][x]=f2[t][x-t]+f2[t-][x-t]
下面这两种情况去掉了1 2和1 1类似的重复情况。
将n个数划分为m个非空集合
f3[t][x]=f[t][x-t]+f[t-][x-]
(最小数为1，去掉一个,如果最小数有多个，由于没有考虑去掉的是哪一个，所以1 ， 1是相同的情况)
将n个数划分为m个可为空的集合
d[m][n]=d[m][n-m]+d[m-][n]
(最小数为0，可能有多个，假设是k个，去k次，跟位置无关，去k次就可去完)
d[m][n]=f3[][n]+f3[][n]+f3[][n]+.....f[k][n]+....f[m][n];
扩展问题：
有n种物品，第i种物品有a[i]个，不同种类的物品可以互相取分，但相同种类的无法区分，
从这些物品中取出m个的话，有多少种取法？
解法1
d[i+][j]
代表将前i种物品中取出j个，并且每种物品最多去a[i]个，
d[i+][j]+=d[i][j-k] <=k<=min(j,a[i]);
解法2
d[i+][j]=d[i+][j-]-d[i][j--a[i]]+d[i][j]
要求得是从前i个物品中取出j个的方案数，由于此题中1 1 2和1 2 1这两种是不同的，
所以不用考虑重复，这样就不能给每个数都减去1，我们可以考虑给第i个数减去1，
a: 当第i个数>=1时，d[i+1][j-1]等于d[i+1][j],然而第i个数的最大值要小于等于a[i]，
再正着看回去，d[i+1][j-1]肯定满足条件，如果给它的第i个数等于a[i],加上1之后，
d[i+1][j]就不满足条件了,所以需要减去d[i][j-1-a[i]];
b: 当第i个数等于0时，d[i][j]=d[i+1][j].
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define maxn 1100
int n,m,MOD;
int d[maxn][maxn];
void init()
{
memset(d,,sizeof(d));
/* for(int i=1;i<=maxn;i++)
{
d[i][1]=1;
d[i][0]=1;
}*/ }
void solve()
{
d[][]=;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
{
if(j>=i)
d[i][j]=(d[i][j-i]+d[i-][j])%MOD;
else
d[i][j]=d[i-][j]%MOD;
}
printf("%d\n",d[m][n]);
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&MOD))
{
init();
solve();
}
return ;
}
扩展问题的代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define maxn 1100
int n,m;
int a[maxn];
int dp[maxn][maxn];
int MOD;
void init()
{
// memset(a,0,sizeof(a));
// memset(dp,0,sizeof(dp));
}
void solve()
{
for(int i=;i<=n;i++)
dp[i][]=; for(int i=;i<n;i++)
for(int j=;j<=m;j++)
{
if(j--a[i] >= )
{
dp[i+][j]=(dp[i+][j-] + dp[i][j] -dp[i][j--a[i] ] + MOD) %MOD;
}
else
dp[i+][j]=(dp[i+][j-] + dp[i][j] ) %MOD;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
printf("%d ",dp[i][j]);
printf("\n");
}
}
int main()
{
// freopen("test.txt","r",stdin);
while(~scanf("%d%d%d",&n,&m,&MOD))
{
init();
for(int i=;i<n;i++)
scanf("%d",&a[i]);
solve();
}
return ;
}