题目链接：?pid=5185题目大意：问按照题目所给的公式，有多少种不同的方法得到n，方法数对m取余题目分析：因为n比较大，直接背包，时间空间都不允许，考虑公式性质，最大的情况下获得n，即1～ma求和，，ma * (ma + 1) / 2 == n化简可以得到ma = (sqrt(8n + 1) – 1) / 2，时间空间复杂度均化为nsqrt(n)，考虑dp[i][j]表示前i个数字合成数字j的种类数，则转移方程为dp[i][j] = dp[i – 1][j – i] + dp[i][j – i]，前i个数字合成j的种类数等于合成j－i时放了i和没放i两种情况的和，dp[0][0] = 1#include <cstdio>#include <cmath>#include <algorithm>using namespace std;int dp[317][50001];int main(){int T, n, m;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){dp[0][0] = 1;scanf("%d %d", &n, &m);int ans = 0, ma = (sqrt(8 * n + 1) – 1) / 2;for(int j = 1; j <= n; j++)for(int i = 1; i <= min(j, ma); i++)dp[i][j] = (dp[i][j – i] + dp[i – 1][j – i]) % m;for(int i = 1; i <= ma; i++)ans = (ans + dp[i][n]) % m;printf("Case #%d: %d\n", ca, ans);}}
梦想，并不奢侈，只要勇敢地迈出第一步。
