Warning: session_start(): open(/tmp/sess_3c9e855eea6c06ad8cbd5bb9423b382b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 常系数齐次线性递推 ======
===== 算法思想 =====
求一个满足 $k$ 阶齐次线性递推数列 $a_{i}$ 的第 $n$ 项，即： $a_{n}=\sum_{i=1}^{k} f_{i}×a_{n-i}$ ，求 $a_{n}$ 。
其中 $n≤10^{9},k≤32000,|f_{i}|,|a_{0},…,a_{k-1}|≤10^{9}$
解法是求用快速幂求 $x^{n}$ 对特征多项式 $p$ 取模的结果。
比如求斐波那契数列的第五项 $fib_{5}$ ，于是我们相当于 $0x^{0}+0x^{1}+…+1x^{5}$。
我们先把 $x^{5}$ 的系数减一，再把 $x^{4}$ 和 $x^{3}$ 系数都加一，从而变成 $0x^{0}+0x^{1}+…+1x^{3}+1x^{4}+0x^{5}$ 。相当于对于 $x^{2}-x-1$ 取模。剩下依次类推。
于是原题相当于求出多项式 $x^{n}$ 对多项式 $x_{k}-p_{1}x_{k-1}-p_{2}x_{k-1}-…-p_{k}$ 取模。
===== 算法实现 =====
#include
#define int long long
using namespace std;
const int N=2000006,GG=3,GI=332748118,mod=998244353;
inline void read(int &X){
X = 0;
int w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
if (w) X = -X;
}
namespace my_f {
int qpow(int a,int b,int m=mod) {
int r=1;
while(b) {
if (b&1) r=r*a%m;
a=a*a%m,b>>=1;
}
return r;
}
int pgg[30],pgi[30];
void init() {
for(register int i=0; i<=23; i++) {
pgg[i]=qpow(GG,(mod-1)>>i);
pgi[i]=qpow(GI,(mod-1)>>i);
}
}
#define ad(x,y) ((x)+(y)>mod?(x)+(y)-mod:(x)+(y))
#define dc(x,y) ((x)-(y)<0?(x)-(y)+mod:(x)-(y))
namespace poly {
int w[N],r[N];
void NTT(int f[N],int lim,int type) {
for(register int i=0; i>1]>>1)|((i&1)?len:0));
NTT(a,lim,1);
NTT(b,lim,1);
for(register int i=0; i>1]>>1)|((i&1)?len:0));
NTT(a,lim,1);
NTT(b,lim,1);
for(register int i=0; i>1]>>1)|((i&1)?len:0));
NTT(b,lim,1);
NTT(Q,lim,1);
for(register int i=0; i>=1;
}
for(int i=0; i