poj 3735 Training little cats 构造矩阵+稀疏矩阵加速连乘+矩阵快速幂

我不是女神ヾ 2022-07-16 05:25 180阅读 0赞

poj 3735 Training little cats 构造矩阵+稀疏矩阵加速连乘 题目链接：[http://poj.org/problem?id=3735][http_poj.org_problem_id_3735]

题面描述：

Training little cats

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;13366</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3293</td> 
  </tr> 
 </tbody> 
</table>

Description

Facer's pet cat just gave birth to a brood of little cats. Having considered the health of those lovely cats, Facer decides to make the cats to do some exercises. Facer has well designed a set of moves for his cats. He is now asking you to supervise the cats to do his exercises. Facer's great exercise for cats contains three different moves:  
g i : Let the ith cat take a peanut.  
e i : Let the ith cat eat all peanuts it have.  
s i j : Let the ith cat and jth cat exchange their peanuts.  
All the cats perform a sequence of these moves and must repeat it m times! Poor cats! Only Facer can come up with such embarrassing idea.  
You have to determine the final number of peanuts each cat have, and directly give them the exact quantity in order to save them.

Input

The input file consists of multiple test cases, ending with three zeroes "0 0 0". For each test case, three integers *n*, *m* and *k* are given firstly, where *n* is the number of cats and *k* is the length of the move sequence. The following *k* lines describe the sequence.  
(*m*≤1,000,000,000, *n*≤100, *k*≤100)

Output

For each test case, output *n* numbers in a single line, representing the numbers of peanuts the cats have.

Sample Input

3 1 6
    g 1
    g 2
    g 2
    s 1 2
    g 3
    e 2
    0 0 0

Sample Output

2 0 1

题目大意：

给n只喵咪分配花生，共有k个分配的操作，重复着k次操作m次，由于m比较大，所以要借助于矩阵连乘来求解。

题目分析：

由于明确使用矩阵快速幂求解，所以，分析题目可得由一个1\*n的矩阵和多个矩阵x相乘之后变为一个1\*n的矩阵，那么这个矩阵x一定是n\*n的，那么就要去构造这个矩阵，构造矩阵的方法如下：

<转>

解题思路：  
我们把刚才那3只猫看做一个矩阵\{a,b,c\},分别代表他们有的花生个数，显然初始是\{0,0,0\}

当进行s操作的时候，我们将初始矩阵乘上一个矩阵，得到的那个矩阵最好也是1行3列的。  
那肯定我们要构造的那个矩阵式3\*3的矩阵

s 1 2交换操作就是\{a,b,c\}\*x=\{b,a,c\}

x=\{0 1 0\}

1 0 0

0 0 1

那么S操作就是这样的，首先将X看做一个单位矩阵，要交换哪两个，只需要交换他们的列就可以了

对于e操作近似于s操作，将e 2举例：\{a,b,c\}\*x=\{a,0,c\}

x=\{1 0 0\}

0 0 0

0 0 1

即将某列置于0

现在问题来了，怎么构造g操作的矩阵。使下面这个等式成立  
g 1操作 \{a,b,c\}\*X=\{a+1,b,c\}  
g 2操作 \{a,b,c\}\*X=\{a,b+1,c\}  
g 3操作 \{a,b,c\}\*X=\{a,b,c+1\}

这样所构造的矩阵会含有a，b，c的值，不可能将构造一个这样的矩阵，这不科学，因为在前面构造s操作与e操作时，我们并不需要知道a，b，c的值

那这样，我们不妨再\{a,b,c\}矩阵多加一个1，这样我们就能实现我们的+1操作了  
要使g 1操作实现\{a,b,c,1\}\*x=\{a+1,b,c,1\}

那么x= 1 0 0 0

0 1 0 0

0 0 1 0

1 0 0 1

当然这样构造矩阵，这样并不影响我们前面的s与e操作

这样一系列操作之后：

![1345427364_4195.jpg][]

而重复m次那么多操作，只是需要将\{0,0,0,1\}\* X^m=\{a,b,c,1\}  
这个时候a，b，c就是我们要的答案，构造X次方只能用模拟去构造，因为操作最多只有100次，所有不费什么时间，现在重要的是X^m

正常的矩阵连乘代码：

mat multi(mat a,mat b)
    {
        mat c;
        for(int i=1; i<=n+1; i++)
        {
            for(int j=1; j<=n+1; j++)
            {
                c.m[i][j]=0;
                for(int k=1; k<=n+1; k++)
                    c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
                //c.m[i][j]%=mod;
            }
        }
        return c;
    }

经过加速的矩阵连乘代码：

mat multi(mat a,mat b)
    {
        mat c;
        memset(c.m,0,sizeof(c.m));
        for(int i=1; i<=n+1; i++)
        {
            for(int j=1; j<=n+1; j++)
            {
                if(a.m[i][j])///加速算法,一定要进行初始化,否则没有效果
                {
                    for(int k=1; k<=n+1; k++)
                        c.m[i][k]+=(a.m[i][j]*b.m[j][k]);
                }
            }
        }
        return c;
    }

代码实现：

代码一：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int maxn=120;
    
    long long a[maxn],ans2[maxn];
    long long n,mm,k;
    
    struct mat
    {
        long long m[maxn][maxn];
    };
    
    mat x;
    
    mat I;
    
    mat multi(mat a,mat b)
    {
        mat c;
        memset(c.m,0,sizeof(c.m));
        for(int i=1; i<=n+1; i++)
        {
            for(int j=1; j<=n+1; j++)
            {
                if(a.m[i][j])///加速算法,一定要进行初始化,否则没有效果
                {
                    for(int k=1; k<=n+1; k++)
                        c.m[i][k]+=(a.m[i][j]*b.m[j][k]);
                }
            }
        }
        return c;
    }
    
    mat power(mat A,long long k)//矩阵快速幂
    {
        mat ans=I,p=A;
        while(k)
        {
            if(k&1)///若k为奇数,
            {
                ans=multi(ans,p);
                k--;
            }
            k>>=1;///k=k/2;
            p=multi(p,p);
        }
        return ans;
    }
    
    int main()
    {
        while(scanf("%lld%lld%lld",&n,&mm,&k)!=EOF)
        {
            getchar();
            if(n==0 && mm==0 && k==0)
                break;
            memset(a,0,sizeof(a));
            memset(ans2,0,sizeof(ans2));
            memset(x.m,0,sizeof(x.m));
            for(int i=1; i<=n+1; i++)
            {
                x.m[i][i]=1;
                I.m[i][i]=1;
            }
            for(int i=0; i<k; i++)
            {
                char c=getchar();
                if(c=='g')
                {
                    int k;
                    scanf("%d",&k);
                    x.m[n+1][k]++;
                }
                else if(c=='e')
                {
                    int k;
                    scanf("%d",&k);
                    for(int i=1; i<=n+1; i++)
                    {
                        x.m[i][k]=0;
                    }
                }
                else
                {
                    int k1,k2;
                    scanf("%d%d",&k1,&k2);
                    long long tmp[maxn];
                    for(int i=1; i<=n+1; i++)
                    {
                        tmp[i]=x.m[i][k1];
                        x.m[i][k1]=x.m[i][k2];
                        x.m[i][k2]=tmp[i];
                    }
                }
                getchar();
            }
            /*for(int i=1;i<=n+1;i++)
            {
                for(int j=1;j<=n+1;j++)
                {
                    cout<<x.m[i][j]<<" ";
                }
                cout<<endl;
            }*/
            mat ans=power(x,mm);
    
            /*for(int i=1; i<=n+1; i++)
            {
                for(int j=1; j<=n+1; j++)
                {
                    cout<<ans.m[i][j]<<" ";
                }
                cout<<endl;
            }*/
    
            a[n+1]=1;///此处可以简化掉
            for(int i=1; i<=n+1; i++)
            {
                long long tmp=0;
                for(int j=1; j<=n+1; j++)
                {
                    tmp+=a[j]*ans.m[j][i];
                }
                ans2[i]=tmp;
            }
            printf("%lld",ans2[1]);
            for(int i=2; i<=n; i++)
                printf(" %lld",ans2[i]);
            printf("\n");
        }
        return 0;
    }

代码二：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int maxn=110;
    
    __int64 n,mm,k;
    
    struct mat
    {
        __int64 m[maxn][maxn];
    };
    
    mat x;
    
    mat I;
    
    mat multi(mat a,mat b)
    {
        mat c;
        memset(c.m,0,sizeof(c.m));
        for(int i=1; i<=n+1; i++)
        {
            for(int j=1; j<=n+1; j++)
            {
                if(a.m[i][j])
                {
                    for(int k=1; k<=n+1; k++)
                    {
                        if(b.m[j][k])///也是加速
                            c.m[i][k]+=(a.m[i][j]*b.m[j][k]);
                    }
                }
            }
        }
        return c;
    }
    
    mat power(mat A,__int64 k)//矩阵快速幂
    {
        mat ans=I,p=A;
        while(k)
        {
            if(k&1)///若k为奇数,
            {
                ans=multi(ans,p);
                k--;
            }
            k>>=1;///k=k/2;
            p=multi(p,p);
        }
        return ans;
    }
    
    int main()
    {
        while(scanf("%I64d%I64d%I64d",&n,&mm,&k)!=EOF)
        {
            getchar();
            if(n==0 && mm==0 && k==0)
                break;
            memset(x.m,0,sizeof(x.m));
            for(int i=1; i<=n+1; i++)
            {
                x.m[i][i]=1;
                I.m[i][i]=1;
            }
    
            for(int i=0; i<k; i++)
            {
                char c=getchar();
                if(c=='g')
                {
                    int k;
                    scanf("%d",&k);
    
                    x.m[n+1][k]++;
                }
                else if(c=='e')
                {
                    int k;
                    scanf("%d",&k);
                    for(int i=1; i<=n+1; i++)
                    {
                        x.m[i][k]=0;
                    }
                }
                else
                {
                    int k1,k2;
                    scanf("%d%d",&k1,&k2);
    
                    /*long long tmp[maxn];
                    for(int i=1; i<=n+1; i++)
                    {
                        tmp[i]=x.m[i][k1];
                        x.m[i][k1]=x.m[i][k2];
                        x.m[i][k2]=tmp[i];
                    }*/
                    for(int i=1;i<=n+1;i++)
                    swap(x.m[i][k1],x.m[i][k2]);
                }
                getchar();
            }
    
            mat ans=power(x,mm);
    
            printf("%I64d",ans.m[n+1][1]);
            for(int i=2; i<=n; i++)
                printf(" %I64d",ans.m[n+1][i]);
            printf("\n");
        }
        return 0;
    }

[http_poj.org_problem_id_3735]: http://poj.org/problem?id=3735
[1345427364_4195.jpg]: https://img-my.csdn.net/uploads/201208/20/1345427364_4195.jpg