POJ – 3735 Training little cats

上一次做矩阵快速幂专题大概是半年前了…..昨天在子扬学长的提醒下决定重开这个专题(假)复习(真预习)。

这不做不知道….一做我还真不会….看到这题的一瞬间我大脑的第一反应是—线段树!然而…..这不是区间更新根本没必要用线段树(≡ω≡.)

这题我是wa了七发才过,最后发现是题目里面EOF的要求是ending with three zeroes . 然后我写的是n&&m&&k,这样m其实是可以为0的但是我这里break掉了 ╮(╯_╰)╭,改成&&(m+n+k)就好了或者直接声明break就好了……以后写题不能为了便利取一些“巧”啊啊啊啊啊。

下面是代码,裸裸的矩阵快速幂。

这里用n+1行单位矩阵表示n个单位的val(peanut)变化,不多解释了,线性代数的知识,m轮操作直接矩阵连乘就好。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,m,k;
struct Matrix
{
    ll mi[150][150];
};

Matrix a;

Matrix Mul(Matrix a,Matrix b)
{
    Matrix c;
    memset(c.mi,0,sizeof(c.mi));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a.mi[i][j]==0)
                continue;
            else
            {
                for(int k=1;k<=n;k++)
                {
                    if(b.mi[j][k]==0)
                        continue;
                    c.mi[i][k]+=a.mi[i][j]*b.mi[j][k];
                }
            }
        }
    }
    return c;
}

Matrix qic_pow(ll m)
{
    Matrix unit;
    memset(unit.mi,0,sizeof(unit.mi));
    for(int i=1;i<=n;i++)
        unit.mi[i][i]=1;
    while(m)
    {
        if(m&1)
            unit=Mul(unit,a);
        a=Mul(a,a);
        m/=2;
    }
    return unit;
}

int main()
{
    while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF&&(m+n+k))
    {
        n++;
        memset(a.mi,0,sizeof(a.mi));
        for(int i=1;i<=n;i++)
            a.mi[i][i]=1;
        char s[5];
        while(k--)
        {
            scanf("%s",s);
            if(s[0]=='g')
            {
                ll x;
                scanf("%lld",&x);
                a.mi[x][n]++;
            }
            if(s[0]=='e')
            {
                ll x;
                scanf("%lld",&x);
                for(int i=1;i<=n;i++)
                    a.mi[x][i]=0;
            }
            if(s[0]=='s')
            {
                ll x,y;
                scanf("%lld%lld",&x,&y);
                ll temp;
                for(int i=1;i<=n;i++)
                {
                    swap(a.mi[x][i],a.mi[y][i]);
                }
            }
        }
        Matrix ans=qic_pow(m);
        for(int i=1;i<n;i++)
        {
            if(i!=n-1)
                printf("%lld ",ans.mi[i][n]);
            else
                printf("%lld\n",ans.mi[i][n]);
        }
    }
}