| 4015 划分数 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
有n个无区别的物品，将他们划分成不超过m组，求出划分方法数模1e9的余数
|
|
输入
|
|
输入共一行：为两个正整数n，m。
|
|
输出
|
|
输出共一行：为方案数。
|
|
输入示例
|
|
4 3
|
|
输出示例
|
|
4
|
|
其他说明
|
|
1<=m,n<=5000
|
题解：余一法
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,mod=1e9;
int d[maxn][maxn],n,m;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void init(){
n=read();m=read();
d[][]=;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
if(j>=i) d[i][j]=d[i-][j]+d[i][j-i],d[i][j]%=mod;
else d[i][j]=d[i-][j];
write(d[m][n]);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}