/ / 题库 /

回文分割

回文分割

测试数据来自 wjszez/1827

【问题描述】
大家都知道回文串吧~ 简单地说就是左右对称的一个串,比如 abcba,werrew。小 s 对回文
串的研究已经够深刻了,现在她转而研究其他方面的回文,比如,数的回文拆分。对于自然
数的拆分,就是把一个自然数 N 用若干个整数之和表示。比如 5=1+2+3+4+5=1+2+1+7+1+2+1。
那么怎样的拆分才算是回文的呢?我们用从归纳的角度来定义数的回文拆分。首先一个数
A=A 是一个回文拆分。其次,一个自然数 N=A+A 或是 N=A+x+A,其中 A 是一个回文拆分,x
是任意一个自然数,这两种也是回文拆分。举个例子,7 的所有回文拆分有:7,
1+5+1,2+3+2,1+1+3+1+1,3+1+3,1+1+1+1+1+1+1。现在小 s 想知道,一个正整数 N 的回文拆
分到底有多少种。由于这个数字可能很大,小 s 只需要你告诉她答案除以1,000,000,007 的
余数的值。
【输入格式】
一行,一个正整数 N
【输出格式】
一行,一个整数 M,为 N 的回文拆分数%(mod) 1,000,000,007 的值
【样例输入 1】
4
【样例输出 1】
4
【样例输入 2】
20
【样例输出 2】
60
【数据范围】
30% 1<=N<=20
100% 1<=N<=1000

信息

ID
1865
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者