tqyaaaaang's Blog

AUTHOR: Tianqi Yang

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

NOI 2017 游记

Day 0 报到日。 中午火车到绍兴。 唉,今年省选炸了,所以只有D类喽,orz tjw & zyd 省队爷啊! 晚上看了看一些好用的shell脚本,感觉在考场上打不出来了。 tjw & zyd写模板,Au的节奏! Day 1 开幕式+笔试日 tjw早上在空间里发说说,说所有点赞的OIer,如果他进了队就请吃三顿饭。大家快去点赞啦,可以免费吃三顿饭呢! 上午开幕式,一堆晦涩难懂的东西,群里面:“暗示题目题意难懂”(手动害怕)???还有dzd迷一般的讲话,被某个群改了一波:   dzd:我要一个D一个D的攒钱   dzd:决不做B,都来买D 下午笔试+试机。感觉赛场环境比WC的要亮堂一些,更加清爽。笔试就是随便考考,~~没有几个不100的吧。。。~~试机也没有什么好试的,反正WC也见过了。 晚上和我校神犇一起打一些数据结构,其它的都还好,NTT错了n多次,是不是暗示我明年进不了National Training Team呢(哈哈今年D类无所谓)。 Day 2 NOI Day 1。 早上大早就醒了,NOI居然是早上8:00,有点早啊,只能靠冰红茶来抵挡瞌睡了(绍兴一中居然没有红牛供应,差评)。结果发现起早了。。。只能回宿舍重新看了一下配置文件等等。。。 然后就机试了,早上听tjw大喊数声“好紧张啊”,搞得我也好慌啊。 看看题面,三道传统题?大致看看题目,这个部分分给的很全啊,…

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} } \)的形式,…

写Blog啦!

终于开始写Blog了。 想写Blog很久了。但是看到中国的那些博客网站,好多广告啊,然后就不太想写了。 听说有自己用VPS搭建这种操作,然后就试试啦! 搭建日志:link 作为算法类Blog,也需要写些算法。许多简单的算法网上有许多,不乏好的博客讲解,随便搜搜就行了,我也就不再重复这些工作了,所以我就只写一些网上比较少的算法,或是缺少讲的比较好的博客的一些算法,我就把这些再写一写,希望更多的人能够理解它。…