Emmm很不想写代码的感觉。

CF392C Yet Another Number Sequence

题目描述

Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:

$ F{1}=1,F{2}=2,F{i}=F{i-1}+F{i-2}$ We’ll define a new number sequence $A{i}(k)$ by the formula:

$ A{i}(k)=F{i}×i^{k} (i>=1). $ In this problem, your task is to calculate the following sum: $A{1}(k)+A{2}(k)+…+A_{n}(k)$ . The answer can be very large, so print it modulo 1000000007 $(10^{9}+7)$

Solution

定义$f(n,k) = \sum\limits_{i=1}^{n}A_i(k)$

大致猜一个推导方向是常系数线性递推。

$f(n,k)=\sum_{i=1}^nF_ii^k$ $=\sum_{i=1}^n(F_{i-1}+F_{i-2})i^k$

二项式定理展开

$\sum_{i=1}^nF_{i-1}\sum_{j=0}^k(i-1)^j\binom kj+\sum_{i=1}^nF_{i-2}\sum_{j=0}^k\binom kj(i-2)^j2^{k-j}$

交换求和顺序

$\sum_{j=0}^k\binom kj\sum_{i=1}^nF_{i-1}(i-1)^j+\sum_{j=0}^k\binom kj2^{k-j}\sum_{i=1}^nF_{i-2}(i-2)^j$

这一步需要注意一下边界情况，$F_0=1,0^0=1$（这里按照IEEE标准）

$\sum_{j=0}^k\binom kj\sum_{i=1}^{n-1}F_ii^j+1+\sum_{j=0}^k\binom kj2^{k-j}\sum_{i=1}^{n-2}F_ii^j+2^k$ $\sum_{j=0}^k\binom kjf(n-1,j)+\sum_{j=0}^k\binom kj2^{k-j}f(n-2,j)+2^k+1$

矩阵快速幂优化即可，注意一下初始状态
时间复杂度$O(k^3\log n)$

#include <iostream>
const int mod = 1000000007;
using LL = long long;
int k, C[50][50], pow[50], num[2][50], K, tot;
void up(int &x, int y) { if ((x += y) >= mod) x -= mod; }
struct matrix {
    int num[83][83];
    matrix operator * (matrix rhs) const {
        matrix res;
        for (int i = 0; i <= K; i++)
            for (int j = 0; j <= K; j++) {
                int ans = 0;
                for (int k = 0; k <= K; k++) up(ans, static_cast<LL> (num[i][k]) * rhs.num[k][j] % mod);
                res.num[i][j] = ans;
            }
        return res;
    }
} base, init;
LL n;
int main() {
    std::cin >> n >> k; K = 2 * k + 2;
    for (int i = 0; i <= k + 1; i++) pow[i] = (1LL << i) % mod;
    for (int i = 0; i <= k; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            up(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
        }
    }
    for (int i = 0; i < 2; i++) for (int j = 0; j <= k; j++) num[i][j] = tot++;
    for (int j = 0; j <= k; j++) {
        for (int p = 0; p <= j; p++)
            base.num[num[0][p]][num[0][j]] = C[j][p];
        for (int p = 0; p <= j; p++)
            base.num[num[1][p]][num[0][j]] = static_cast<LL> (C[j][p]) * pow[j - p] % mod;
        base.num[K][num[0][j]] = pow[j] + 1;
        base.num[num[0][j]][num[1][j]] = 1;
    }
    base.num[K][K] = 1;
    for (int j = 0; j <= k; j++) {
        init.num[0][num[0][j]] = (1 + pow[j + 1]) % mod;
        init.num[0][num[1][j]] = 1;
    }
    init.num[0][K] = 1;
    if (n == 1) std::printf("%d\n", init.num[0][num[1][k]]);
    else {
        for (----n; n; n >>= 1, base = base * base) if (n & 1) init = init * base;
        std::printf("%d\n", init.num[0][num[0][k]]);
    }
    return 0;
}

其实还可以用更优的方法。

定义$F,G$分别是斐波那契数列的初始矩阵和转移矩阵。比较特殊$(FG^{i-1}){1,1} = G^{i-1}{1,1}$

$F(2n,k) = \sum\limits{i=1}^{n} + G^{n}{1,1}\sum\limits{i=1}^{n}G^{i}{1,1}(i+n)^k$

恒等变换后等于

$F(n,k)+G^n_{1,1}\sum\limits_{j=0}^k \dbinom{k}{j} n^{k-j} F(n,j)$

时间复杂度是$O(8klogn)$,实现的时候因为$n$不是2的次幂，所以先处理到$2^k$大于$n$即可。

每个转移的复杂度是常数。

很中档的一道题。。