P4451 [国家集训队]整数的lqp拆分

拆分整数$n$,$a_1+a_2..a_m=n$。求$\sum \prod F_{a_i}$

考虑$dp[i]$为$n$拆分的值。

$$dp[i]=\sum_{j<i}dp[j]\times F[i-j],dp[0]=1,F[0]=0$$

$G=F*G+1,F=\frac{x}{1-x-x^2}$

$$G=\frac{1-x-x^2}{1-2x-x^2}=1+\frac{x}{1-2x-x^2}=1+(\frac{-1}{(x-(-1+\sqrt{2}))(x-(-1-\sqrt{2}))})\\ \\=1+(\frac{1}{((-1-\sqrt{2})x+1)((-1+\sqrt{2})x+1)})\\ \\=1+(\frac{1}{1-(1+\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x})\frac{1}{2\sqrt{2}}$$ $$G(x)=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$$

二次剩余搞下即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int e2 = 59713600;

int qpow(int a, int x)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        x >>= 1;
    }
    return res;
}
int main()
{
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {

        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (1ll * x * 10 % (mod - 1) + c - '0') % (mod - 1), c = getchar();
    cout << 1ll * (qpow(e2 + 1, x) - qpow(mod - e2 + 1, x) + mod) % mod * qpow(4, mod - 2) % mod * e2 % mod << endl;
}