hdu 2276 Kiki & Little Kiki 2（矩阵递推）

hdu 2276 Kiki & Little Kiki 2（矩阵递推）

这题真心很棒，展现了矩阵递推的优雅。

​​由左右影响可以写出状态转移矩阵：

假设串的长度是4：

假设原串是0110，那么新串就是

那么第二次后的串就该是在这个基础上右边再乘上状态转移矩阵：

第N次后的串就是

嗯，水到渠成。

（下面的取模不用位运算也行，直接使用%，多花时间16MS。当然，不能和其他大神的0ms相比。哈哈哈）

#include #include #include using namespace std;int n,m;struct matrix{ int m[105][105];}I,A;matrix multi(matrix a,matrix b){ matrix c; for(int i=0;i>=1; } return ans;}int main(){ //freopen("cin.txt","r",stdin); char str[105]; int s[105]; int res[105]; for(int i=0;i<105;i++) I.m[i][i]=1; while(cin>>m){ scanf("%s",str); n=strlen(str); A=I; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。