高度由习惯堆积

分类 算法:矩阵快速幂 下的文章

HDU6155 Subsequence Count

题目给出一个长度为n的01串S,有Q个操作:1.翻转区间[l,r](0变1,1变0)2.求区间[l,r]有多少不同的子串思路这是一道好题,首先考虑没有修改操作的dp状态,则$dp[i][j]$表示到了第$i$个位置,结尾为$j$的串的方案数则我们可以得到以下递推关系:$$ dp[i][j]=dp[i-1][0]+dp[i-1][1]+1,j==S[i]\\ dp[i][!j]=dp[i-1]...
February 17, 2019

HDU5564 Clarke and digits

前置知识$dp[i][j][k]$表示$i$长,$mod7=j$,这个位置选了$k$的方案数。$dp[i+1][(j*10+x)mod7][x]+=dp[i][j][y];//x+y!=K​$$Ma.a[i][j]=1$表示$i$状态->$j$状态可以转移如果设$ans=qkpow(Ma,K)$。则$ans.a[i][j]$表示走$K$步之后状态$i$到状态$j$的方案数。如果对这个不...
February 10, 2019

Uva10870 Recurrences(矩阵快速幂)

题目考虑递推关系式$f(n)=a1*f(n-1)+a2*f(n-2)+....+ad*f(n-d)$,计算f(n)%m 【输入格式】 输入包含多组测试数据。每组数据第一行为三个整数d,n,m(1<=d<=15,1<=n<=2^31-1,1<=m<=46340)。第二行包含d个非负整数a1,a2.....ad。第三行为d个非负整数f(1),f(2).....