Skip to content

13044: 【原3044】palin

题目

题目描述

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

Description

大家都知道回文串吧~ 简单地说就是左右对称的一个串,比如 abcba,werrew。小 s 对回文串的研究已

经够深刻了,现在她转而研究其他方面的回文,比如,数的回文拆分。对于自然数的拆分,就是把一个

自然数 N 用若干个整数之和表示。比如 15=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 只需要你告诉她答案 mod 1,000,000,007 的

值。

Input Format

一行,一个正整数 N

Output Format

一行,一个整数 M,为 N 的回文拆分数 mod 1,000,000,007 的值

Sample Input

20

Sample Output

60

Hints

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

About Testdata

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 getAnswer(int n) {
    if (answers[n] != 0)
        return answers[n];
    ll ans = 1;
    if (n % 2 == 0) {
        ans += getAnswer(n / 2);
        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);
        }
    }
    answers[n] = ans % p;
    return ans % p;
}

int main() {
    int tmp;
    cin >> tmp;
    cout << getAnswer(tmp) << endl;
}

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];
}