Oiclass P2107 题解

这道题的思路非常奇怪（至少我觉得是这样）

你需要把它当做一道找规律题

\(\Huge{进入正题}\)

先看题目：

小 S 想计算一个自然数 n \((n < 2000)\) 的所有回文分解的个数 \(\% 1000000007\) 的值。

我们来看一下 \(1\to10\) 的所有整数的回文分解个数。简单在草稿纸上枚举可以发现，分别是：

\[ 1,2,2,4,4,6,6,10,10,14 \]

可以看出，奇数位（\(1,3,5,7,9\)）的数是它的上一位（除了 \(1\)）。那么偶数位的什么呢？我们要从数列里面找，可以看出：

\[ \begin{array}{l} 4 = 2 + 2 \newline 6 = 4 + 2 \newline 10 = 6 + 4 \newline 14 = 10 + 4 \end{array} \]

那么究竟是哪个数加上哪个数呢？如果把这个数列看作 \(F\) 那么如下：

\[ \begin{array}{l} 4 = F_{4} = 2 + 2 = F_{2} + F_{2} = F_{4 - 2} + F_{4 \times \frac{1}{2}} \newline 6 = F_{6} = 4 + 2 = F_{4} + F_{3} = F_{6 - 2} + F_{6 \times \frac{1}{2}} \newline 同理 ............. \end{array} \]

所以，\(F_{n} = F_{n - 2} + F_{n \times \frac{1}{2}} \ \ \ \ (n \ge 4)\)

那么我们就可以写代码了，直接写一个循环递推就可以了，非常短小精悍。但是写的时候要注意，要先给 \(F_{1},\ F_{2},\ F_{3}\) 赋值，赋值后就可以计算了记得计算的时候 \(\% \ 1000000007\)，代码如下：

#include <iostream>

using namespace std;
unsigned long long n, a[10000000];

int main() {
    cin >> n;
    a[1] = 1;
    a[2] = a[3] = 2;
    for (int i = 4; i <= n; i++){
        if (i % 2 == 0) {
            a[i] = (a[i - 2] + a[i / 2]) % 1000000007;
        } else {
            a[i] = a[i - 1];
        }
    }
    cout << a[n];
}

直接 \(\tiny轻松 \Huge AC\)