分拆数 && hdu 4651 && hdu 4658

迷南。 2022-06-08 02:13 675阅读 0赞

**转载自http://blog.csdn.net/zhoufenqin/article/details/9821617**

**分拆数**

在将分拆数之前先介绍一点五边形数

[http://en.wikipedia.org/wiki/Pentagonal\_number][http_en.wikipedia.org_wiki_Pentagonal_number]

![Center][]

1. 五边形数是能排成[五边形][Link 1]的[多边形数][Link 2]。

第n个五边形数公式：p(n)=(3\*n^2-n)/2

前几个五边形数：[1][], [5][], [12][], [22][], [35][], [51][], [70][], [92][], [117][], 145, 176, 210, 247, 287, 330, 376, 425, 477, 532, 590, 651, 715, 782, 852, 925, [1001][] .........

2. 广义五边形数：

n的取值0,1,-1,2,-2,3,-3.......

前几个广义五边形数：0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, 176, 187, 210, 222, 247, 260, 287, 301, 330......

3. 中心五边形数：

![Center 1][]

![Center 2][]

4.中心六边形数

中心六边形数跟广义五边形数有较大的关系，见图

![Center 3][]

![Center 4][]

(相邻两个广义五边形数之和)

5. 五边形数测试

利用以下的公式可以测试一个正整数x是否是五边形数（此处不考虑广义五边形数）：

![Center 5][]

若n是[自然数][Link 3]，则x是五边形数，而且恰为第n个五边形数。

若n不是[自然数][Link 3]，则x不是五边形数。

进入正题：**分拆数**

将一个数用一个或多个正整数的无序和来表示

例如4的分拆有5种：4 , 3+1 , 2+2 , 2+1+1 , 1+1+1+1

1. 限制分拆

给一些分拆加限制条件。例如8的分拆有22种，

其中分拆的数中全部都是奇数的有6种：7+1, 5+3, 5+1+1+1, 3+3+1+1, 3+1+1+1+1+1, 1+1+1+1+1+1+1+1;

同样，若要求8分拆的数中是两两不同的也有6种：8, 7+1, 6+2, 5+3, 5+2+1, 4+3+1

已证明一个数的分拆中满足以上两种条件的个数是相同的，详见[http://en.wikipedia.org/wiki/Glaisher%27s\_theorem][http_en.wikipedia.org_wiki_Glaisher_27s_theorem]

一些有关限制分拆的结论：

·n的分拆数中最大部分为m的个数=把n分拆成m部分的个数

![Center 6][]

如图，左边最大部分m=3，等于把n拆成3部分(右图)   把图转置即可

·n的分拆数中每一部分都小于等于m的个数=把n分成m份或更小

·n的分拆数中每部分的数都相等的个数=n 的因子个数

Eg. 6=2+2+2, 6=3+3,6=1+1+1+1+1+1

·n的分拆数中每部分都是1或2(或者把n分拆成1或2部分)的个数=floor(n/2+1);

Eg. 6=1+1+1+1+1+1, 6=1+1+1+1+2, 6=1+1+2+2, 6=2+2+2

·n的分拆数中每部分都是1或2或3(或者把n分拆成1或2或3部分)的个数=(n+3)^2/12;

2. 生成函数

![Center 7][]

因为![Center 8][] ，右边的表达式等于乘积![Center 9][](母函数)

Pn 等于方程n=a1+2\*a2+3\*a3+...+n\*an 的非负整数解a1,a2...an 的个数。

若是用母函数的方法去做，n很大不容易解出来，继续往下看

定义P(k,n)为：将n表示成>=k 的数之和。Eg P(3,6): 6=3+3

1) 当最小的数为k时，p(k,n) = p(k,n-k)。即在n-k表示成>=k的数之和的情况下再加入一个k，情况还是不变

2) 当最小的数>k时，则至少最小的数为k+1，p(k,n)=p(k+1,n);

所以p(k,n)=p(k,n-k)+p(k+1,n)。k>n 时，p(k,n)=0,p(n,n)=1;

![Center 10][]eg： p(9)=p(1,8)+p(2,7)+p(3,6)+p(4,5);

得到下表：

前几个分拆数1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42 ,56,77,101,135......

如果是按p(k,n)=p(k+1,n)+p(k,n-k) 来算，复杂度仍是0(n^2),往下看

![Center 7][]

右边的分母是欧拉函数，可写成![Center 11][]

可以发现等式右边x的指数为扩展五边形数,可根据之前介绍的扩展五边形公式算得p(n)=(3\*n^2-n)/2，系数符号为(-1)^(m+1)

于是 p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15)  − p(k − 22) − ...

Eg p(10)=p(9)+p(8)-p(5)-p(3)。复杂度降低了

/\*

总结：

五边形数：0, 1, 2, 5, 7, 12, 15, 22, 26, 35....

对应下标：0, 1, -1, 2, -2, 3, -3, 4, -4 , 5.....

![Center 12][]

所以 可以在O(N^1.5)的时间内求出p(1),p(2),...p(n)。

\*/

**Hdu 4658 **要求拆分的数中每个数出现的次数不能大于等于k次，则

![Center 13][]

已经求得，现在看Q(x^k)会怎么样

例如，当n=8，k=4时

满足指数为8的乘积之和为：![Center 14][]

所以将8拆分的数中每个数的个数小于4的有16个，分别为

8,1+7,1+1+6,1+1+1+5,6+2,1+5+2,1+1+4+2,1+1+1+3+2,4+2+2,1+3+2+2,1+1+2+2+2,1+1+3+3,1+4+3,5+3,2+3+3,4+4

hdu 4651

[http://acm.hdu.edu.cn/showproblem.php?pid=4651][http_acm.hdu.edu.cn_showproblem.php_pid_4651]

代码有点捉急。。

**\[cpp\]**  [view plain][]   [copy][view plain]

1. \#include<iostream>  
2. \#include<cstdio>  
3. \#include<cstring>  
4. \#include<string>  
5. \#include<cmath>  
6. \#include<algorithm>  
7.   
8. **using** **namespace** std;  
9.   
10. **typedef** **\_\_int64** LL;  
11. **const** **int** maxn=100010;  
12. **const** LL MOD=1000000007;  
13. LL dp\[maxn\];  
14. LL Five(LL x)  
15. \{  
16.     LL ans=3\*x\*x-x;  
17.     **return** ans/2;  
18. \}  
19. **void** \_init()  
20. \{  
21.     dp\[0\]=1;  
22.     **for**(**int** i=1;i<maxn;i++)  
23.     \{  
24.         **for**(**int** j=1;;j++)  
25.         \{  
26.             LL k=Five(j);//获取五边形数  
27.             **if**(k<=i)  
28.             \{  
29.                 **if**(j%2==0)//判断奇偶从而判断系数为正还是为负  
30.                     dp\[i\]=(dp\[i\]-dp\[i-k\]);  
31.                 **else**  
32.                     dp\[i\]=(dp\[i\]+dp\[i-k\]);  
33.                 **if**(dp\[i\]>=MOD) dp\[i\]%=MOD;  
34.                 **if**(dp\[i\]<0) dp\[i\]+=MOD;  
35.                 k=Five(-1\*j);  
36.                 **if**(k<=i)  
37.                 \{  
38.                     **if**(j%2==0)  
39.                         dp\[i\]=(dp\[i\]-dp\[i-k\]);  
40.                     **else**  
41.                         dp\[i\]=(dp\[i\]+dp\[i-k\]);  
42.                     **if**(dp\[i\]>=MOD) dp\[i\]%=MOD;  
43.                      **if**(dp\[i\]<0) dp\[i\]+=MOD;  
44.                 \}  
45.                 **else**  
46.                     **break**;  
47.             \}  
48.             **else**  
49.                 **break**;  
50.         \}  
51.     \}  
52. \}  
53. **int** main()  
54. \{  
55.     \_init();  
56.     **int** T,n;  
57.     scanf("%d",&T);  
58.     **while**(T--)  
59.     \{  
60.         scanf("%d",&n);  
61.         printf("%I64d\\n",dp\[n\]);  
62.     \}  
63.     **return** 0;  
64. \}

hdu 4658

[http://acm.hdu.edu.cn/showproblem.php?pid=4658][http_acm.hdu.edu.cn_showproblem.php_pid_4658]

**\[cpp\]**  [view plain][]   [copy][view plain]

1. \#include<iostream>  
2. \#include<cstdio>  
3. \#include<cstring>  
4. \#include<string>  
5. \#include<cmath>  
6. \#include<algorithm>  
7.   
8. **using** **namespace** std;  
9.   
10. **typedef** **\_\_int64** LL;  
11. **const** **int** Maxn=100010;  
12. **const** LL MOD=1000000007;  
13. LL Q\[Maxn\],P\[Maxn\];  
14. LL GetQ(LL x)  
15. \{  
16.     LL ans=(LL)x\*x\*3-x;  
17.     **return** (ans/2)%MOD;  
18. \}  
19. **void** \_init()  
20. \{  
21.     Q\[0\]=0;  
22.     **for**(**int** i=1;i<Maxn;i++)  
23.     \{  
24.         **if**(i&1) Q\[i\]=GetQ(i/2+1);  
25.         **else** Q\[i\]=GetQ(i/2\*(-1));  
26.     \}  
27.     P\[0\]=P\[1\]=1;  
28.     **for**(**int** i=2;i<Maxn;i++)  
29.     \{  
30.         **for**(**int** j=1;;j++)  
31.         \{  
32.             **if**(Q\[j\]>i) **break**;  
33.             **int** t=j;  
34.             **if**(t&1) t=t/2+1;  
35.             **else** t=t/2;  
36.             **if**(t&1)  
37.                 P\[i\]=(P\[i\]+P\[i-Q\[j\]\]);  
38.             **else**  
39.                 P\[i\]=(P\[i\]-P\[i-Q\[j\]\]);  
40.             **if**(P\[i\]>=MOD) P\[i\]%=MOD;  
41.             **if**(P\[i\]<0) P\[i\]+=MOD;  
42.         \}  
43.     \}  
44. \}  
45. **void** solved(LL n,LL k)  
46. \{  
47.     LL ans=0;  
48.     **for**(**int** i=0;;i++)  
49.     \{  
50.         **if**(Q\[i\]\*k>n) **break**;  
51.         **int** t=i;  
52.         **if**(t&1) t=t/2+1;  
53.         **else** t=t/2;  
54.         **if**(t&1) ans=(ans-P\[n-Q\[i\]\*k\]);  
55.         **else** ans=(ans+P\[n-Q\[i\]\*k\]);  
56.         **if**(ans>=MOD) ans%=MOD;  
57.         **if**(ans<0) ans+=MOD;  
58.     \}  
59.     printf("%I64d\\n",ans);  
60. \}  
61. **int** main()  
62. \{  
63.     \_init();  
64.     **int** T;  
65.     LL n,k;  
66.     scanf("%d",&T);  
67.     **while**(T--)  
68.     \{  
69.         scanf("%I64d%I64d",&n,&k);  
70.         solved(n,k);  
71.     \}  
72.     **return** 0;  
73. \}  
74.

[http_en.wikipedia.org_wiki_Pentagonal_number]: http://en.wikipedia.org/wiki/Pentagonal_number
[Center]: /images/20220608/366a554e80bf46099ab6d8aa9abbaa3b.png
[Link 1]: http://zh.wikipedia.org/wiki/%E4%BA%94%E9%82%8A%E5%BD%A2
[Link 2]: http://zh.wikipedia.org/wiki/%E5%A4%9A%E9%82%8A%E5%BD%A2%E6%95%B8
[1]: http://en.wikipedia.org/wiki/1_%28number%29
[5]: http://en.wikipedia.org/wiki/5_%28number%29
[12]: http://en.wikipedia.org/wiki/12_%28number%29
[22]: http://en.wikipedia.org/wiki/22_%28number%29
[35]: http://en.wikipedia.org/wiki/35_%28number%29
[51]: http://en.wikipedia.org/wiki/51_%28number%29
[70]: http://en.wikipedia.org/wiki/70_%28number%29
[92]: http://en.wikipedia.org/wiki/92_%28number%29
[117]: http://en.wikipedia.org/wiki/117_%28number%29
[1001]: http://en.wikipedia.org/wiki/1001_%28number%29
[Center 1]: /images/20220608/3177600b6d594622bf58848d70931b63.png
[Center 2]: /images/20220608/6510efabd962483d96c864bac806b54d.png
[Center 3]: /images/20220608/3177e60a9c88474c8608e64b91290e53.png
[Center 4]: /images/20220608/a9e9140b81f446c9b7834b4d4a8778a6.png
[Center 5]: /images/20220608/5583e4a6aea64dfdb6a332a04c0b4f11.png
[Link 3]: http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B8
[http_en.wikipedia.org_wiki_Glaisher_27s_theorem]: http://en.wikipedia.org/wiki/Glaisher'%20rel=
[Center 6]: /images/20220608/fea16e03536946c0aa6b54786376703e.png
[Center 7]: /images/20220608/24f6fa6b113c413e97ae74025c3ec45a.png
[Center 8]: https://img-blog.csdn.net/20130807194237593?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhvdWZlbnFpbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 9]: /images/20220608/6dfc5b53f4f34b519031d695b4d3e841.png
[Center 10]: /images/20220608/5cdfc7ca03ef4d4f8013d4769eb48fc7.png
[Center 11]: /images/20220608/51e2462c0a0c47e7a3800c25289941db.png
[Center 12]: /images/20220608/58e2817245af41b5ab84dc15363e11fb.png
[Center 13]: /images/20220608/3a65b03412d34a04bd1e50f48af8171e.png
[Center 14]: /images/20220608/ce0a931b0ef841d9b99bf0b071bae862.png
[http_acm.hdu.edu.cn_showproblem.php_pid_4651]: http://acm.hdu.edu.cn/showproblem.php?pid=4651
[view plain]: http://blog.csdn.net/zhoufenqin/article/details/9821617#
[http_acm.hdu.edu.cn_showproblem.php_pid_4658]: http://acm.hdu.edu.cn/showproblem.php?pid=4658