|
Equation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 64 Accepted Submission(s): 20
Problem Description Gorwin is very interested in equations. Nowadays she gets an equation like this
x1+x2+x3+?+xn=n
, and here
0≤xi≤nfor1≤i≤nxi≤xi+1≤xi+1for1≤i≤n?1
For a certain
n
, Gorwin wants to know how many combinations of
xi
satisfies above condition.
For the answer may be very large, you are expected output the result after it modular
m
.
Input Multi test cases. The first line of the file is an integer
T
indicates the number of test cases.
In the next
T
lines, every line contain two integer
n,m
.
[Technical Specification]
1≤T<20
1≤n≤50000
1≤m≤1000000000
Output For each case output should occupies one line, the output format is Case #id: ans, here id is the data number starting from 1, ans is the result you are expected to output.
See the samples for more details. Sample Input
2
3 100
5 100 Sample Output
Case #1: 2
Case #2: 3 Source BestCoder Round #32
题目链接：http://acm.hdu.edu.cn/showproblem.php?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
#include
#include
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); } }
|