题目链接：Project Euler 427

如果一个数列 $\{s_{i}\}$ 的长度为 $n$ 且元素 $s_{i}$ 均为 $[1, n]$ 范围内的整数，那么该数列是「$n$ 数列」。显然有 $n^{n}$ 个不同的「$n$ 数列」。

对于任意的数列 $\{s_{i}\}$，定义 $L(s)$ 为最长的相同连续子序列的长度。

定义 $f(n)$ 为所有的「$n$ 数列」的 $L(s)$ 之和。

求 $f(7\ 500\ 000) \bmod (10^{9} + 9)$。

Solution

设 $f(i, j)$ 表示长度为 $i$ 且 $L(s) < j$ 的数列个数，容斥可以得到转移：

$$ f(i, j) = n \cdot f(i - 1, j) - (n - 1) \cdot f(i - j, j) $$

对于固定的 $j$，考虑其组合意义：每个点 $i$ 出发可以到达 $i + 1$ 和 $i + j$，其中到 $i + 1$ 有 $n$ 条边，到 $i + j$ 有 $1 - n$ 条边，求 $0 \rightarrow n$ 的路径总数。

枚举第 $2$ 种边的数量为 $k$ 条，则第 $1$ 种边的数量为 $n - jk$ 条。

$$ f(j) = \sum_{k = 0}^{\left\lfloor\frac{n}{j}\right\rfloor} (1 - n)^{k} n^{n - jk} \binom{n - jk + k}{k} $$

那么答案为：

$$ \begin{align*} & \sum_{i = 1}^{n} i \cdot [f(n, i + 1) - f(n, i)] \\ = & n \cdot f(n, n + 1) - \sum_{i = 1}^{n} f(n, i)\\ = & n^{n + 1} - \sum_{i = 1}^{n} f(n, i) \end{align*} $$

特别注意的是，上述转移方程是不完善的，当 $i = j$ 时，后一项 $f(i - j, j)$ 的系数为 $n$ 而不是 $n - 1$（因为没有前面数字的限制），需要额外计算。

注意到计算 $f(i)$ 的复杂度为 $\mathcal O\left(\frac{n}{i}\right)$，则总复杂度为调和级数。

时间复杂度：$\mathcal O(n \log n)$，其中 $n = 7\ 500\ 000$。

Code

答案：$97138867$。

#include <bits/stdc++.h>
typedef long long int64;

const int N = 7.5e6 + 5, MOD = 1e9 + 9;
int n, x, fac[N], inv[N], ifac[N], pw1[N], pw2[N];

inline void add(int &x, const int y) {
    (x += y) >= MOD && (x -= MOD);
}
void init(int n, int k1, int k2) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = (int64)fac[i - 1] * i % MOD;
    }
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (int64)(MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    ifac[0] = 1;
    for (int i = 1; i <= n; i++) {
        ifac[i] = (int64)ifac[i - 1] * inv[i] % MOD;
    }
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw1[i] = (int64)pw1[i - 1] * k1 % MOD;
        pw2[i] = (int64)pw2[i - 1] * k2 % MOD;
    }
}
inline int binom(int n, int m) {
    return (int64)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
inline int solve(int n, int k) {
    int ans = 0;
    for (int i = 0; i * k <= n; i++) {
        add(ans, (int64)pw1[n - i * k] * pw2[i] % MOD * binom(n - i * k + i, i) % MOD);
    }
    return ans;
}
int main() {
    n = 7500000;
    init(n, n, 1 - n + MOD);
    int ans = 1;
    for (int i = 0; i <= n; i++) {
        ans = (int64)ans * n % MOD;
    }
    for (int i = 1; i <= n; i++) {
        add(ans, solve(n - i, i));
        add(ans, MOD - solve(n, i));
    }
    printf("%d\n", ans);
    return 0;
}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1aah2gzw656ai