[NOI2008]志愿者招募

转载自byvoid

这道题正确的解法是构造网络,求网络最小费用最大流,但是模型隐藏得较深,不易想到。

构造网络是该题的关键,以下面一个例子说明构图的方法和解释。

[luogu4834]萨塔尼亚的期末考试

这里有 oeis 的解释,但是我看不懂。

题目大意:快速地求

ans=𝑛𝑖=1(𝑖fib(𝑖))𝑛(𝑛+1)2

𝑛𝑖=1fib(𝑖)=1+fib(1)+fib(2)++fib(𝑛)1[1+(1)==0]=(fib(2)+fib(1))+fib(3)++fib(𝑛)1[fib(1)==fib(2)]=(fib(3)+fib(2))+fib(4)++fib(𝑛)1[fib(1)+fib(2)==fib(3)]==fib(𝑛+2)1𝑛𝑖=1𝑖fib(𝑖)=𝑛𝑛𝑖=1fib(𝑖)𝑛1𝑖=1𝑖𝑗=1fib(𝑗)=𝑛(fib(𝑛+2)1)𝑛1𝑖=1(fib(𝑖+2)1)=𝑛fib(𝑛+2)𝑛(𝑛1𝑖=1fib(𝑖+2))+(𝑛1)=𝑛fib(𝑛+2)(𝑛+1𝑖=1fib(𝑖)2)1=𝑛fib(𝑛+2)(fib(𝑛+3)12)1=𝑛fib(𝑛+2)fib(𝑛+3)+2

写一个矩阵快速幂就可以解决问题,时间复杂度𝑂(𝑇log2(𝑛)),但是不出意料的 T 掉了

观察一下结果,可以发现我们分别对 ans 中两个相邻的 fib 值进行计算,这并没有利用好矩阵乘法的性质

回想一下最初学习矩阵快速幂的时候,老师演算 fib 的时候是一个1×2的矩阵乘上2×2的矩阵,像这样:

[fib(𝑛)fib(𝑛1)][1110]=[fib(𝑛1)fib(𝑛2)]

我们用老师最初讲的方法来计算 fib 的值,可以节省一半的时间,在加上2×2的矩阵乘法不用 for 循环,就可以轻松切过这道题了~

UPD: 老师最后写的方法并不是错的,在只求一次或者不相邻的项中会显得更快一些,但这并不代表我们可以忘掉原来讲的那种方法(这真的是一道好题)

最终的矩阵为:

[10][1110]𝑛+3

NTT用到的各种素数

转载自 miskcoo

是这样的,这几天在写 NTT,由于是在模意义下的,需要各种素数……

然后就打了个表方便以后查了。

如果𝑟(2𝑘+1)是个素数,那么在mod𝑟(2𝑘+1)意义下,可以处理2𝑘以内规模的数据。

2281701377=17×227+1是一个挺好的数,平方刚好不会爆 long long。

1004535809=479×221+1加起来刚好不会爆 int 也不错。

还有就是 UOJ 常用的998244353=119×223+1

打表方法:对于每个𝑘,找到最小𝑟满足𝑟(2𝑘+1)是素数(𝑔mod𝑟(2𝑘+1)的原根)。

Educational Codeforces Round 46

一场简单题之战,就是比做题的速度以及正确率(感觉出题人去看球赛去了)