tqyaaaaang's Blog

TAG: 题解

tqyaaaaang's Blog.

Navigation

UOJ - 126 - 快餐店 ( 环套树DP )

题目链接:http://uoj.ac/problem/126 详细题解在代码后面 思路 环套树DP(废话) 考虑树的情况怎么做 考虑如何拓展到环上 代码 #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <bitset> #include <algorithm&…

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