这题说的是
x[1]+x[2]+x[3]+…+x[n]=n, 这里
0 <= x[i] <= n && 1 <= i <= n
x[i] <= x[i+1] <= x[i]+1 && 1 <= i <= n-1
对于一个给定的n,Gorwin想要知道有多少xi的组合满足上述等式。由于结果比较大，输出答案对m取余的结果就行。
n<=50000
经过分析我们知道第一个数必须是 0 或者 1 ，如果是0 那么我们分析，第一个开始为1 的数字， 后面必须连续到结尾都是大于等于1 的个数，这么想前面的那些前导0将变得毫无意义，只是连续非0长度的个数，我们在计算中会计算出来的。现在我们有一个方案 dp[i][j] 表示前n项到达j的方案 数， 这样我们 有 n＊n＊n 的状态转移， 好了现在这个复杂度过大，我们可以想办法把它降下来，我们知道连续的数字 各个都不同最多才 sqrt(n)个,现在就降了一点了， 再想想我们摈弃了 0 那么意思说第一个数是从1开始的，那么我们就不用害怕他会使用超过n个数字来达到和为n 我们知道最多也就是使用n个分别都为1 ，其余的都得小于1，那么现在我们是不是又降了最外层的一个n ， 现在复杂度变成了 nsqrt(n);
我们再整理一下， dp[i][j] 表示使用1-i个数字组成和为j的个数，（因为我们可以不讨论使用了多少个数字，因为他肯定不会超过n）时间复杂度刚好
dp[i][j]=( dp[i][j-i] + dp[i-1][j-i] )%m
//
// main.cpp
// hdu5185c++
//
// Created by opas on 15/3/15.
// Copyright (c) 2015年 opas. All rights reserved.
// #include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = ;
const int maxm =;
int dp[maxm][maxn];
int main(int argc, const char * argv[]) {
// insert code here...
int cas;
scanf("%d",&cas);
int n,m;
for(int cc =; cc<= cas; ++cc){
scanf("%d%d",&n,&m); memset(dp, , sizeof(dp));
int k=,G=n;
while(k*(+k)<=G*) k++;
k--;
dp[][]=;
for(int i=; i<=k; ++i)
for(int j=i; j <= n ; ++ j ){
dp[i][j]= (dp[i-][j-i]+dp[i][j-i])%m;
}
int ans=;
for(int i=; i <= k; ++i )
ans= (ans+dp[i][n])%m;
printf("Case #%d: %d\n",cc, ans); }
return ;
}