bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

2160: 拉拉队排练

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1938  Solved: 743
[Submit][Status][Discuss]

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行,每个人手中都举了一个写有26个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K,代表的东西在题目描述中已经叙述。接下来一行为n个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数,代表题目描述中所写的乘积除以19930726的余数,如果总的和谐小群体个数小于K,输出一个整数-1。

Sample Input

5 3
ababa

Sample Output

45
【样例说明】
和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b,前三个长度的乘积为。

HINT

总共20个测试点,数据范围满足: 

 

 

思路:

直接PAM.

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

codeforces 385 E. Bear in the Field (先记录想法)

题目链接

题意:

有一只熊,初始在(sx,sy)处,如果当前的位置在(x,y),那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处, dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1],k表示的是某个点的花丛数目。

初始点(x,y)的花丛数为x+y,每经过一个时间,所有点的花丛数增加1.

所以,k[i] = x[i] + y[i] + i-1,现在问经过时间t后,熊的位置在哪里。也就是x[t],y[t]的值。

思路:

我们不妨先只考虑x方向的,因为y方向完全相同。

观察x[t]的式子, x[t] = (x[t-1] + dx[t-1] -1) % n +1。。这个%n之后+1简直蛋疼得一逼。。。

我们不妨构造g[t] = x[t]-1,这样原式子就变成了 g[t] = (g[t-1] + dx[t-1]) %n …看起来爽了很多。。。

观察式子g[t] = (g[t-1] + dx[t-1]) % n,我们发现这是一个前缀和的形式。

根据在hdu4686解题报告  中提到的经验,对于求和的式子,我们只需要考虑每一项的构造法。

因此问题转化成构造矩阵dx[t]

dx[t] = k[t-1] + dx[t-1]

其中k[t] = x[t] + y[t] + t-1,我们写成gx[t]和gy[t]的形式

k[t] = gx[t] + gy[t] + t + 1

k[t-1] = gx[t-1] + gy[t-1] + t

因此可以得到k[t-1]与k[t]之间的递推关系: k[t] = k[t-1] + dx[t-1] + dy[t-1] + 1

观察到k[t]的表达式中同时包含dx,dy项,因此之前考虑的单独处理x和y的想法应该是行不通的。我们考虑同事处理x,y。

 

 

UVA – 10518 How Many Calls? (构造矩阵,快速幂)

题目链接

题意:

求f[n] = f[n-1] + f[n-2] + 1,在b(10000)进制下的最后一位数字的十进制表示。

思路:

构造矩阵即可,M矩阵是一个33的矩阵,M1矩阵是一个31的矩阵。。很easy,就不说了。

写题解的目的是,对于这种要求b进制下,最后一位或者最后两位的数字的十进制表示的问题,其实就是在说,取模的数是base或者base^2

1A美滋滋

 

hdu 4686 Arc of Dream (构造矩阵,快速幂)

hdu4686题目链接

题意:

An Arc of Dream is a curve defined by following function:


where
0 = A0
i = a i-1AX+AY
0 = B0
i = b i-1
BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

 

思路:

看n的1E18的范围也知道是矩阵快速幂。。

难点还是构造矩阵。

构造矩阵主要凭借经验,但是还是有一些规律可循:

  1. 对于求和的式子,如 s[n] = sum{F[1]..F[n]}类似的式子,我们只需要考虑如何构造F[n]即可。
  2. 尽量将要构造的表达式展开成,第n项,与前面项(第n-1项等)有关的形式。
  3. 观察2中展开的表达式的系数,每一个系数都亚奥出现在转移矩阵M中。
  4. 观察2中展开的表达式的项,基本每一项都要整体或者以其他形式出现在初始矩阵M1中
  5. 我们并不很关心初始项。
  6. 难点其实在于构造M1矩阵,也就是说哪些项是重要的。一般而言,可能有的项是,s[n],f[n],常数项,以及为了构造出f[n]的辅助项。

对于这道题:

 

然后矩阵快速幂即可。

1A

 

uva 10870 – Recurrences (矩阵加速线性递推式)

uva10870题目链接

题意:

f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d

给出f[1]..f[d],a[1]..a[d],问 f[n]%m是多少。

思路:

构造矩阵,加速递推式。

趁着这道题说一下一般的构造法。

转移矩阵M(d*d)的构造方法是,最后一行倒序写a[1]..a[d], 除去第一列和最后一行外,用1填充对角线,其余的为0.

初始矩阵M1(d*1)的构造方法是从上到下,f[1]..f[d]即可。

需要注意的是

最后答案是 (M^(n-d))*M1.mat[d-1][0] (由于经常出现的是d=2的递推式,因此注意不要把此式子的d,写成不够一般化的错误的2

 

uva 10655 – Contemplation! Algebra (构造矩阵,快速幂)

uva10655题目链接

题意:

给出a+b和ab的值,问a^n+b^n

思路:

构造矩阵,手写一下很显然…

转移矩阵M=[0 , 1]

[-q,p ]

初始矩阵M1=[p           ]

[p^2-2*q]

快速幂即可。

有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。

如果用p=0&&q=0作为终止条件,那么就会将三个输入,但p==0&&q==0的情况错误得终止…

正确的做法是 while (~scanf(“%lld%lld%lld”,&p,&q,&n)==3)

 

 

 

【dp专题001】bzoj 1009: [HNOI2008]GT考试 (字符串上dp+kmp+矩阵加速线性递推式)

 

1009: [HNOI2008]GT考试

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 3127  Solved: 1926
[Submit][Status][Discuss]

Description

  阿申准备报名参加GT考试,准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2…Am(0<=Ai<=9)有M位,不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为
0

Input

  第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

  阿申想知道不出现不吉利数字的号码有多少种,输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81

思路:

这次总算想对了状态表示:dp[i][j] 表示当前处理到第i位,最后j位与不吉利串相同的方案数。

然后此时考虑转移,也就是观察第i+1位。

根据第i+1位字符的不同,转移到的 位置也不相同。

从dp[i][j] 可以转移到dp[i+1][k],这种转移表现为dp[i+1][k] += dp[i][j] (k取决于第i+1位字符)

我们可以用f[i+1][k]+=f[i][j]*trans[j][k],trans[j][k]表示串s后j位与不吉利串前j位相同,

添加一个字符后后k位与不吉利串前k位相同的方案数。

%e9%80%89%e5%8c%ba_001

就是说中间的那一部式子可以化简成矩阵的形式。。因此整个递推式就成了矩阵乘法的形式。

tran数组可以用kmp预处理出来。

 

重点是注意体会在字符串上dp的思想。

 

acdream oj 1124 喵喵的遗憾 (斐波那契数列循环节)

题目链接

题意:

F0 = 1 , F1 = 1 , F2 = 2 , Fn = Fn-1+Fn-2

求:

FFFn Mod P

( 也就是 F[ F[ F[n] ] ]  % P )

思路:原来这是适牛出的题2333.

需要注意的是p可能为1,因此n==0或者1的时候,特判要输出1%p而不是1.

其他的没了。就是求斐波那契数列循环节的经典做法。

 

hdu 4291 A Short problem (矩阵快速幂+广义斐波那契循环节||暴力找循环节)

题目链接

题意:

Given n (1 <= n <= 1018), You should solve for

g(g(g(n))) mod 109 + 7

where

g(n) = 3g(n – 1) + g(n – 2)
 

g(1) = 1
 

g(0) = 0
思路:找循环节。首先由于模数固定,可以暴力一下找到循环节。

得到1E9+7的循环节是222222224,222222224的循环节是183120.

然后三次矩阵快速幂就行了。

需要注意每次都要判断那一层的n是否为0和1。

暴力解法:

再来一个比较一般的做法:

参考递推式循环节

Acdreamer的博客_广义Fibonacci数列找循环节

摘重点:

今天早上起来后,看了下代码,为什么要判断5是不是p的模二次剩余呢,为什么是5呢

想了想,5对于斐波那契数列来讲,不就是x^2=x+1的delta么,那么这题的递推式是x^2=3*x+1,delta=3*3+4=13,然后我就把勒让德符号判断二次剩余那里改成13,然后对应的暴力出13及13以内的素数对应的循环节,交了一发,AC了

 

 

      所以综上所述:

是模的二次剩余时,枚举的因子

是模的二次非剩余时,枚举的因子

对于第二种非剩余的情况,理论上是枚举(p+1)(p-1)的因子,实际上常常只是枚举2*(p+1)的因子

对于c=5的情况,是有定理:

screenshot-from-2016-10-31-21-23-45

不过对于c不等于5的情况。。。该结论是否一定成立呢…感觉不是很好证,求指教。

 

hdu 1005 Number Sequence (矩阵快速幂加速线性递推式)

题目链接

题意:A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

思路:矩阵加速线性递推式。

这题第一次看是2012年11月2333,当时用pascal写的

 

hdu 3221 Brute-force Algorithm (矩阵快速幂+指数循环节)

题目链接

 

题意:给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2]

思路:一眼题,和hdu4549很类似hdu4549解题报告

不同的是这道题中p不一定是质数(其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数,又用费马小定理化简了一下,这道理%phi(p)即可)

还有这道题让我知道了

首先我们知道指数循环节公式,也就是所谓的降幂公式为:a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c),(ps:后面的限制条件,在x<phi(c)的时候,该式子依然正确,只不过增加了运算复杂度。。。? 存疑)

括号里的话是错误的。只有当x<phi(c)的时候,这个公式才成立。

这道题就是反例,不加判断会wa。

 

 

 

BZOJ 4547: Hdu5171 小奇的集合 (矩阵快速幂)

4547: Hdu5171 小奇的集合

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 263  Solved: 113
[Submit][Status][Discuss]

Description

 有一个大小为n的可重集S,小奇每次操作可以加入一个数a+b(a,b均属于S),求k次操作后它可获得的S的和的最大

值。(数据保证这个值为非负数)

Input

第一行有两个整数n,k表示初始元素数量和操作数,第二行包含n个整数表示初始时可重集的元素。

对于100%的数据,有 n<=10^5,k<=10^9,|ai|<=10^5

Output

输出一个整数,表示和的最大值。答案对10000007取模。

Sample Input

2 2
3 6

Sample Output

33

HINT

Source

思路:同hdu 5171的区别在于,a可能为负数。

同样是设a0为次大值,a1为最大值。

根据a0,a1的正负分类讨论。

如果a1<0(此时a0一定也小于0)那么每次操作都是a0+a1,因为越加越小。

如果a0<0,需要计算需要几次运算,使得a0>=0。设需要num次。

原因是,类斐波那契数列的性质可以对于正数,也可以对于负数,但是如果有正数有负数,性质是不满足的。

因此如果num>k,说明一直都是负数,直接运算即可,如果num<=k,就需要先把负数部分用等差数列的方法处理掉。

然后再用矩阵快速幂的方法计算剩下的k-num次。

 

hdu 5171 GTY’s birthday gift (矩阵快速幂)

题目链接

题意:给出n,k,以及n个正数,把n个数放在一个集合里,进行k次操作,每次操作取最大的数和次大的数放进集合。问k次操作结束后,集合中所有数的和。

思路:假设初始时刻,次大和最大分别为a0,a1,那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn

最后求和。

 

screenshot-from-2016-10-25-18-48-09

利用这个性质。。。

我们直接构造完矩阵。。。求出F(n+2)即可。。

需要注意。。。矩阵中每一项是小于1E7+7的。。。矩乘的时候会爆int…

所以mat要用LL存。。我好傻啊。。。

 

 

hdu 4965 Fast Matrix Calculation (矩阵快速幂,2014多校#9)

题目链接

题意:Step 1: Calculate a new N*N matrix C = A*B.
Step 2: Calculate M = C^(N*N).
Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’.
Step 4: Calculate the sum of all the elements in M’.

思路: 水题。。就一个trick…

朴素的矩阵乘法的复杂度是n^3的。。。按照题目的顺序求的话。。。。求M矩阵时会超时。。。(而且1000*1000的数组也不能放到结构体里…?

我们可以根据矩阵乘法的结合律。

M = (A*B)^(N*N) = A * (B*A)^(N*N-1) * B

然后就可以搞了。