P17571 「FAOI-R(-2)」数列计数 2024
Genius_Star
·
·
题解
看到 Bingxiu2 把这题秒了，来看了下这题，给个不太一样的做法。
同 trick 题：CF1864H。
思路：
先定义 f_i 表示以 i 结尾的合法序列数量，然后列出生成函数：
F(x) = \sum_{i \ge 1} f_i x^i
转移显然考虑刷表转移，如果以 i 结尾，下一个可以是 [i + 1, 2i]，对应到生成函数上，于是：
\begin{aligned} F(x) &= f_1x + \sum_{i \ge 1} f_i x^i (x + \cdots + x^i) \\ &= x + \sum_{i \ge 1} f_ix^{i + 1} (1 + \cdots + x^{i - 1}) \\ &= x + \sum_{i \ge 1} f_ix^{i + 1} \frac{1 - x^i}{1 - x} \\ &= x + \frac{x}{1 - x} (\sum_{i \ge 1} f_ix^i - \sum_{i \ge 1} f^ix^{2i}) \\ &=x + \frac{x}{1 - x}(F(x) - F(x^2))\end{aligned}
整理得到：
(2x - 1) F(x) = xF(x^2) + x(x - 1)
提一嘴，刚开始我还是想求封闭形式的，但是发现求出来是一坨，感觉不太能做，Bingxiu2 还是太强了……
显然对比一下系数，于是得到了 f_1 = f_2 = 1，递推式是（k \ge 2）：
\begin{cases} f_{2k} = 2 f_{2k - 1} \\ f_{2k + 1} = 2 f_{2k} - f_k\end{cases}
我们要快速求 f_n。
考虑令 a_k = f_{2k - 1}，所以 f_{2k} = 2a_k，于是 f_{2k + 1} = a_{k + 1} = 4a_k - f_k，初始 a_1 = a_2 = 1。我们求 f_n，可以根据奇偶性判定求某个 a_m。
通项的容易的，因为 a_n = 4a_{n - 1} - f_{n - 1}(n \ge 3)，考虑全部同时除以 4^n 得到：
\frac{a_n}{4^n} = \frac{a_{n - 1}}{4^{n - 1}} - \frac{f_{n - 1}}{4^n}
因为 n \ge 3，可以看作一路从 a_2 加上来，即：
\frac{a_n}{4^n} = \frac{a_2}{4^2} - \sum_{i = 3}^n \frac{f_{i - 1}}{4^i}
因为 a_2 = 1，于是：
\begin{aligned} a_n &= 4^{n - 2} - 4^n \sum_{i = 2}^{n - 1} \frac{f_i}{4^{i + 1}} \\ &= 4^{n - 2} - 4^{n - 1} \sum_{i = 2}^{n - 1} \frac{f_i}{4^i} \\ &= 2 \cdot 4^{n - 2} - 4^{n - 1} \sum_{i = 1}^{n - 1} \frac{f_i}{4^i}\end{aligned}
于是你发现要算一个 f_i 的带权前缀和的形式，于是定义：
F(n, k) = \sum_{i = 1}^n f_i k^i
于是答案 a_n = 2 \cdot 4^{n - 2} - 4^{n - 1} F(n - 1, \frac{1}{4})；然后考虑如何求 F？定义一个辅助的 G 来帮助转移：
G(n, k) = \sum_{i = 1}^n a_i k^i
于是对于 F(n, k) 可以分奇偶拆分一下：
\begin{aligned} F(n, k) &= \sum_{i = 1}^n f_i k^i \\ &= \sum_{i = 1}^{\lceil \frac{n}{2} \rceil} a_i k^{2i - 1} + \sum_{i = 1}^{\lfloor \frac{n}{2} \rfloor} 2a_i k^{2i} - [n \ge 2] k^2\\ &= \frac{1}{k}\sum_{i = 1}^{\lceil \frac{n}{2} \rceil} a_i k^{2i} + 2\sum_{i = 1}^{\lfloor \frac{n}{2} \rfloor} a_i k^{2i} - [n \ge 2]k^2 \\ &= \frac{1}{k} G(\lceil \frac{n}{2} \rceil, k^2) + 2G(\lfloor \frac{n}{2} \rfloor, k^2) - [n \ge 2]k^2\end{aligned}
注意这后面减去的是因为 f_2 \ne 2a_1 所以要把多的减去。
然后对于 G(n, k)，也把它用 F 表示出来看看（令 q = \frac{1}{4}）：
\begin{aligned} G(n, k) &= \sum_{m = 1}^n a_m k^m \\ &= k + \sum_{m = 2}^n (2 \cdot 4^{m - 2} - 4^{m - 1} F(m - 1, q))k^m \\ &= k + 2 \sum_{m = 2}^n 4^{m - 2} k^m - \sum_{m = 2}^n 4^{m - 1} F(m - 1, q)k^m \\ &= k + 2k^2 \frac{1 - (4k)^{n - 1}}{1 - 4k} - XXX\end{aligned}
然后：
\begin{aligned} XXX &= \sum_{m = 2}^n 4^{m - 1} F(m - 1, q)k^m \\ &= \frac{1}{4} \sum_{m = 2}^n (4k)^m \sum_{i = 1}^{m - 1} f_i q^i \\ &= \frac{1}{4} \sum_{i = 1}^{n - 1} f_i q^i\sum_{m = i + 1}^n (4k)^m \\ &= \frac{1}{4} \sum_{i = 1}^{n - 1} f_i q^i (4k)^{i + 1} \frac{1 - (4k)^{n - i}}{1 - 4k} \\ &= \frac{1}{1 - 4k} \sum_{i = 1}^{n - 1} f_i k^{i + 1} (1 - (4k)^{n - i}) \\ &= \frac{1}{1 - 4k}\left( k \sum_{i = 1}^{n - 1} f_i k^i - k^{n + 1} 4^n \sum_{i = 1}^{n - 1} f_i 4^{- i}\right) \\ &= \frac{1}{1 - 4k}\left( k F(n - 1, k) - k^{n + 1} 4^n F(n - 1, \frac{1}{4})\right) \\ &= \frac{k}{1 - 4k}(F(n - 1, k) - (4k)^n F(n - 1, \frac{1}{4}))\end{aligned}
最终：
G(n, k) = k + 2k^2 \frac{1 - (4k)^{n - 1}}{1 - 4k} -\frac{k}{1 - 4k}(F(n - 1, k) - (4k)^n F(n - 1, \frac{1}{4}))
分析一下复杂度，按 F 的递归分层，最多 O(\log n) 层，对于每一层内，k 只能有 O(\log n) 种，而每层的 n 只有 O(1) 种；算上中间快速幂的复杂度，是 O(T \log^3 n) 的，可以通过。
实际上这里有一些细节，如果 1 - 4k = 0 的话，即 k = \frac{1}{4} 时上面的式子是有问题的，但是你发现，每次调用 G 的 k 只是 (\frac{1}{4})^{2^t} 这样形式的，先算一下 4 的阶是 \delta_p(4)，那么要解 2^t \equiv 1 \pmod {\delta_p(4)}，于是 t 最小解是 \delta_{\delta_p(4)}(2)，容易验证其大于 60，所以实际上不会出现这个问题。
还是因为每次调用 G 的 k 只是 (\frac{1}{4})^{2^t} 这样形式的，所以可以提前把每个 t 对应的值预处理出来（逆元同理），然后直接光速幂预处理，就可以做到 O(\sqrt p \log n + T \log^2 n)；但是没必要，不卡常。
完整代码：
#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int mod = 1e9 + 7;
inline ll read(){
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int add(int x, int y){
return (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void getdec(int &x, int y){
x = (x < y) ? (x - y + mod) : (x - y);
}
inline int dec(int x, int y){
return (x < y) ? (x - y + mod) : (x - y);
}
inline int qpow(int a, ll b){
b %= (mod - 1);
int ans = 1;
while(b){
if(b & 1)
ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return ans;
}
inline int inv(int x){
return qpow(x, mod - 2);
}
int T, inv4;
ll n;
inline int F(ll n, int k);
inline int G(ll n, int k);
map<pair<ll, int>, int> mpF, mpG;
inline int F(ll n, int k){
if(n <= 0)
return 0;
if(n == 1)
return k;
if(mpF.count({n, k}))
return mpF[{n, k}];
return mpF[{n, k}] = dec(add(1ll * inv(k) * G((n + 1) >> 1, 1ll * k * k % mod) % mod, 2ll * G(n >> 1, 1ll * k * k % mod) % mod), 1ll * k * k % mod);
}
inline int G(ll n, int k){
if(n <= 0)
return 0;
if(mpG.count({n, k}))
return mpG[{n, k}];
int r = 4ll * k % mod, ir = inv(dec(1, r));
return mpG[{n, k}] = dec(add(k, 2ll * k % mod * k % mod * dec(1, qpow(r, n - 1)) % mod * ir % mod), 1ll * k * ir % mod * dec(F(n - 1, k), 1ll * qpow(r, n) * F(n - 1, inv4) % mod) % mod);
}
inline int geta(ll n){
if(n <= 2)
return 1;
return dec(2ll * qpow(4, n - 2) % mod, 1ll * qpow(4, n - 1) * F(n - 1, inv4) % mod);
}
inline int getf(ll n){
if(n <= 3)
return 1;
if(n & 1)
return geta((n + 1) >> 1);
else
return 2ll * geta(n >> 1) % mod;
}
inline void solve(){
n = read();
write(getf(n));
putchar('\n');
}
int main(){
inv4 = qpow(4, mod - 2);
T = read();
while(T--)
solve();
return 0;
}