Partition
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 842 Accepted Submission(s): 478
Problem Description
How many ways can the numbers 1 to 15 be added together to make 15? The technical term for what you are asking is the "number of partition" which is often called P(n). A partition of n is a collection of positive integers (not necessarily distinct) whose sum equals n.
Now, I will give you a number n, and please tell me P(n) mod 1000000007.
Now, I will give you a number n, and please tell me P(n) mod 1000000007.
Input
The first line contains a number T(1 ≤ T ≤ 100), which is the number of the case number. The next T lines, each line contains a number n(1 ≤ n ≤ 105) you need to consider.
Output
For each n, output P(n) in a single line.
Sample Input
45111519
Sample Output
756176490
Source
1 /**
2
3 1 2 5 7 12 15 22 26
4 **/
5
6 #include<iostream>
7 #include<stdio.h>
8 #include<cstring>
9 #include<cstdlib>
10 using namespace std;
11 typedef __int64 LL;
12 const int maxn = 1e5+1;
13 LL p = 1000000007;
14 LL dp[maxn];
15 LL five1[1002];
16 LL five2[1002];
17 void init()
18 {
19 int i,j,t;
20 for(LL k=1;k<=1000;k++)
21 five1[k] = k*(3*k-1)/2;
22 for(LL k=1;k<=1000;k++)
23 five2[k] = k*(3*k+1)/2;
24
25 dp[0]=1;
26 for(i=1;i<maxn;i++)
27 {
28 dp[i] = 0;
29 j=1;
30 t=1;
31 while(1)
32 {
33 if(i - five1[t]>=0)
34 {
35 dp[i] =dp[i] + j*dp[i-five1[t]] ;
36 }
37 else break;
38
39 dp[i] = (dp[i]%p+p)%p;
40
41 if( i - five2[t]>=0)
42 {
43 dp[i] = dp[i] + j*dp[i-five2[t]] ;
44 }
45 else break;
46
47 dp[i] = (dp[i]%p+p)%p;
48
49 j = -j;
50 t++;
51 }
52 dp[i] = (dp[i]%p+p)%p;
53 }
54 }
55 int main()
56 {
57 int T,n;
58 init();
59 scanf("%d",&T);
60 while(T--)
61 {
62 scanf("%d",&n);
63 printf("%I64d ",dp[n]);
64 }
65 return 0;
66 }
2
3 1 2 5 7 12 15 22 26
4 **/
5
6 #include<iostream>
7 #include<stdio.h>
8 #include<cstring>
9 #include<cstdlib>
10 using namespace std;
11 typedef __int64 LL;
12 const int maxn = 1e5+1;
13 LL p = 1000000007;
14 LL dp[maxn];
15 LL five1[1002];
16 LL five2[1002];
17 void init()
18 {
19 int i,j,t;
20 for(LL k=1;k<=1000;k++)
21 five1[k] = k*(3*k-1)/2;
22 for(LL k=1;k<=1000;k++)
23 five2[k] = k*(3*k+1)/2;
24
25 dp[0]=1;
26 for(i=1;i<maxn;i++)
27 {
28 dp[i] = 0;
29 j=1;
30 t=1;
31 while(1)
32 {
33 if(i - five1[t]>=0)
34 {
35 dp[i] =dp[i] + j*dp[i-five1[t]] ;
36 }
37 else break;
38
39 dp[i] = (dp[i]%p+p)%p;
40
41 if( i - five2[t]>=0)
42 {
43 dp[i] = dp[i] + j*dp[i-five2[t]] ;
44 }
45 else break;
46
47 dp[i] = (dp[i]%p+p)%p;
48
49 j = -j;
50 t++;
51 }
52 dp[i] = (dp[i]%p+p)%p;
53 }
54 }
55 int main()
56 {
57 int T,n;
58 init();
59 scanf("%d",&T);
60 while(T--)
61 {
62 scanf("%d",&n);
63 printf("%I64d ",dp[n]);
64 }
65 return 0;
66 }