tqyaaaaang's Blog

TAG: FFT

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>…