tqyaaaaang's Blog

TAG: 特征多项式

tqyaaaaang's Blog.

Navigation

HDU 4914 ( 特征多项式+FFT )

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4914 题意 给定n, a, b, p, q,定义\(f(k)\)如下: $$ f(k)= \begin{cases} 1 & k <= 0 \\ a * f(k-p) + b * f(k-q) & k > 0 \end{cases} $$ 求\(f(n)\)。 解法 模板题。用特征多项式优化一下矩阵乘法,然后用FFT优化多项式乘法就行了。 不会特征多项式的看这里 代码 #include <bits/stdc++.h> using namespace std; #define LL long long #define LD long double #define SC(t,x) static_cast<t>…

POJ 2118 ( 特征多项式 )

题目链接:http://poj.org/problem?id=2118 解法 这题其实是矩乘的模板题,这里就不讲了,讲特征多项式优化的方法。 如果不会特征多项式的看这里 然后直接上就行了。 代码 // I/O stream #include <iostream> #include <iomanip> // Algorithms & Maths #include <cmath> #include <numeric> #include <algorithm> // C headers #include <cstdlib> #include <cstdio> // String #include <string> #include <cstring> // STL #include <vector> #include <deque> #include <list> #include <stack>…

特征多项式优化线性递推

【特征多项式优化线性递推】 比较推荐这一篇论文:矩阵乘法递推的优化 大概只需要看第三部分就行了 【线性递推】 特征多项式可以用来优化一些线性递推,一般是给定前k项\({x_1}...{x_k}\),以及向量\({a_1}...{a_k}\),满足下列递推式: $$ {x_n} = \sum_{i=1}^{k} { {a_i} * {x_{n-i}} }\ \ \ \ \ ( n > k ) $$ 问题是求\(x_n\) 这当然可以用矩阵乘法+快速幂来做,复杂度: \(\Theta(k^3\ log\ n)\),这是NOIP难度,就不说了。 【特征多项式】 可以写出矩阵快速幂时候的转移矩阵\(M\)的特征多项式,就可以得到 $$ {M^n} = \sum_{i=1}^{k} { {a_i} * {M^{n-i}} } \tag{1} $$ 具体证明可以参考开头给出的那篇论文。(但是其实只需要把这个式子记下来就行了) 有了这个式子,就可以把所有\(M^n\)表示成\( \sum_{i=1}^{k} { {b_i} * {M^i} } \)的形式,…