hdu2276(构建矩阵)

2017年02月24日 9点热度 0人点赞 0条评论

Kiki & Little Kiki 2

Time Limit: 2000/1000 MS(Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s):2517    Accepted Submission(s): 1312

ProblemDescription

There are n lights in a circle numbered from 1 to n. The left oflight 1 is light n, and the left of light k (1< k<= n) is the lightk-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 noton, turn on it) at t+1 second (t >= 0), if the left of light i is on!!! Given the initiation state, pleasefind all lights’ state
after M second. (2<= n <= 100, 1<= M<= 10^8)

 

 

Input

The input contains one or more data sets. The first line of eachdata 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 alllights
in the circle from 1 to n.
If the ith character of T is '1', it means the light i is on, otherwise thelight is off.

 

 

Output

For each data set, output all lights' state at m seconds in oneline. It only contains character '0' and '1.

 

 

SampleInput

1
0101111
10
100000001

 

 

SampleOutput

1111000
001000010

 

 

Source

HDU 8th Programming Contest Site1

#include
#include
#include
using namespace std;
int m,n,ans[102][102];
void fun()
{
    int t[102][102],a[102][102];
    memcpy(a,ans,sizeof(a));
    m--;
    while(m)
    {
        if(m&1)
        {
            memcpy(t,ans,sizeof(ans));
            memset(ans,0,sizeof(ans));
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                {
                    for(int k=1; k<=n; k++)
                        ans[i][j]+=t[i][k]*a[k][j];
                    ans[i][j]%=2;
                }
        }
        memcpy(t,a,sizeof(a));
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                for(int k=1; k<=n; k++)
                    a[i][j]+=t[i][k]*t[k][j];
                a[i][j]%=2;
            }
        m>>=1;
    }
}
int main()
{
    char s[102];
    int st[102],tt[102];
    while(~scanf("%d",&m))
    {
        scanf("%s",s);
        n=strlen(s);
        for(int i=0; i
未经允许不得转载!hdu2276(构建矩阵)

update

纸上得来终觉浅, 绝知此事须躬行。