首页 > ACM题库 > HDU-杭电 > hdu 2276 Kiki & Little Kiki 2-快速幂-[解题报告]C++
2014
01-04

hdu 2276 Kiki & Little Kiki 2-快速幂-[解题报告]C++

Kiki & Little Kiki 2

问题描述 :

There are n lights in a circle numbered from 1 to n. The left of light 1 is light n, and the left of light k (1< k<= n) is the light k-1.At time of 0, some of them turn on, and others turn off.
Change the state of light i (if it’s on, turn off it; if it is not on, turn on it) at t+1 second (t >= 0), if the left of light i is on !!! Given the initiation state, please find all lights’ state after M second. (2<= n <= 100, 1<= M<= 10^8)

输入:

The input contains one or more data sets. The first line of each data set is an integer m indicate the time, the second line will be a string T, only contains ’0′ and ’1′ , and its length n will not exceed 100. It means all lights in the circle from 1 to n.
If the ith character of T is ’1′, it means the light i is on, otherwise the light is off.

输出:

The input contains one or more data sets. The first line of each data set is an integer m indicate the time, the second line will be a string T, only contains ’0′ and ’1′ , and its length n will not exceed 100. It means all lights in the circle from 1 to n.
If the ith character of T is ’1′, it means the light i is on, otherwise the light is off.

样例输入:

1
0101111
10
100000001

样例输出:

1111000
001000010

点击打开hdu 2276

思路: 矩阵快速幂

分析:

1 题目给定一个01字符串然后进行m次的变换,变换的规则是:如果当前位置i的左边是1(题目说了是个圆,下标为0的左边是n-1),那么i就要改变状态0->1 , 1->0

   比如当前的状态为100101那么一秒过后的状态为010111

2 假设0/1串的长度为n,保存在a数组,下标从0开始

   根据上面的规则我们发现可以得出一秒过后的状态即为a[i] = (a[i]+a[i-1])%2 , 对于a[0] = (a[0]+a[n-1])%2

   那么我们就可以就能够找到递推的式子

   1 1 0 0….     a0        a1

   0 1 1 0…  *  a1   =   a2

   ……….1 1     …..      …..

   1 0 0…..1     an-1    a0

3 但是我们最后要求的是a0 a1 …. an-1 , 所以我们应该把矩阵的第一行和最和一行调换一下,然后进行m次的快速幂即可

4 由于最后的结果是mod2的结果,因此我们可以把所有的*和+运算全部改成&和^

5 由于初始的矩阵是一个循环同构的矩阵,因此我们可以每次先求出第一行,然后在递推出第二行,那么这样就从O(n^3)降到O(n^2)

代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-30                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 105;

int n , len;
char str[MAXN];

struct Matrix{
    int mat[MAXN][MAXN]; 
    Matrix operator*(const Matrix& m)const{
        Matrix tmp;
        for(int i = 0 ; i < len ; i++){
            tmp.mat[0][i] = 0;
            for(int j = 0 ; j < len ; j++)
                tmp.mat[0][i] ^= (mat[0][j]&m.mat[j][i]);
        } 
        for(int i = 1 ; i < len ; i++)
            for(int j = 0; j < len ; j++)
                tmp.mat[i][j] = tmp.mat[i-1][(j-1+len)%len];
        return tmp;
    }
};

void solve(){
    len = strlen(str);

    Matrix m , ans;
    memset(m.mat , 0 , sizeof(m.mat));
    for(int i = 1 ; i < len ; i++)
        m.mat[i][i] = m.mat[i][i-1] = 1;
    m.mat[0][0] = m.mat[0][len-1] = 1;

    memset(ans.mat , 0 , sizeof(ans.mat));
    for(int i = 0 ; i < len ; i++)
        ans.mat[i][i] = 1;
    while(n){
        if(n&1)
            ans = ans*m;
        n >>= 1;
        m = m*m;
    }
    for(int i = 0 ; i < len ; i++){
        int x = 0;
        for(int k = 0 ; k < len ; k++)
            x ^= ans.mat[i][k]&(str[k]-'0');
        printf("%d" , x);
    }
    puts("");
}

int main(){
    while(scanf("%d%s" , &n , str) != EOF)
        solve();
    return 0;
}

解题转自:http://blog.csdn.net/chenguolinblog/article/details/10308407


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false