# 13044: 【原3044】palin

### 题目描述

author: cherry 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3044

## Description

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 只需要你告诉她答案 mod 1,000,000,007 的

## Sample Input

``````20
``````

## Sample Output

``````60
``````

## Hints

``````尝试找规律或者递推、递归解决问题
``````

``````30% 1<=N<=20
100% 1<=N<=1000
``````

## Limits

Time limit: 1000ms, memory limit: 50000kb.

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/3/18.
//
// 递归+保存

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <sstream>

using namespace std;
using ll=long long;

constexpr int p = 1000000007;

static const auto _____ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();

ll pow(ll x, ll y) {
if (y == 0) return 1;
ll z = pow(x, y / 2) % p;
if (y % 2 == 0) return z * z % p;
else return z * z % p * x % p;
}

ll answers[1005] = {0, 1, 2, 2};

ll ans = 1;
if (n % 2 == 0) {
for (int i = 2; i < n; i += 2) {
ans += getAnswer((n - i) / 2);
}
} else {
for (int i = 1; i < n; i += 2) {
ans += getAnswer((n - i) / 2);
}
}
return ans % p;
}

int main() {
int tmp;
cin >> tmp;
}
``````

## FineArtz's solution

``````/* palin */
#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long f[1005] = {0};

int main(){
int n;
cin >> n;
f[1] = 1;
for (int i = 2; i <= n; ++i){
if (i % 2 == 0){
f[i] = (1 + f[i / 2]) % MOD;
for (int j = 2; j < i; j += 2){
f[i] = (f[i] + f[(i - j) / 2]) % MOD;
}
}
else{
f[i] = 1;
for (int j = 1; j <= i; j += 2){
f[i] = (f[i] + f[(i - j) / 2]) % MOD;
}
}
}
cout << f[n] << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
using namespace std;

constexpr long long mod = (long long)(1e9 + 7);

long long ans_data[1009] = { 0 };

int main() {
ans_data[0] = 1;
ans_data[1] = 1;
long long num;
cin >> num;
for (long long i = 2; i <= num; ++i) {
for (long long j = i; j >= 0; j -= 2)
ans_data[i] = (ans_data[i] + ans_data[(i - j) / 2]) % mod;
}
cout << ans_data[num];

return 0;
}
``````

## q4x3's solution

``````/**
* dp
* f[n] = f[1] + f[2] + ... + f[n / 2]
* 注意long long
**/
#include <iostream>

using namespace std;

long long N, f[1010];

int main() {
cin >> N;
f[0] = 1;
f[1] = 1;
for(int i = 2;i <= N;++ i) {
for(int j = 0;j <= i >> 1;++ j) {
f[i] += f[j];
f[i] %= 1000000007;
}
}
cout << f[N] << endl;
}
``````

## skyzh's solution

``````#include <iostream>
using namespace std;

int d_m_n[1000] = { 0 };
const int M = 1000000007;

int main() {
int N;
cin >> N;
d_m_n[0] = d_m_n[1] = 1;
for (int i = 2; i <= N; i++) {
for (int j = i / 2; j >= 0; j -= 1) {
d_m_n[i] = (d_m_n[j] + d_m_n[i]) % M;
}
}
cout << d_m_n[N] << endl;
return 0;
}
``````

## victrid's solution

``````#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 1) {
cout << '1';
return 0;
}
int* ans = new int[n + 1]();
ans[0]   = 1;
ans[1]   = 2;
for (int i = 2; i <= n; i++) {
for (int j = 1; 2 * j <= i; j++) {
ans[i] += ans[j];
ans[i] %= 1000000007;
}
}
cout << ans[n];
}
``````