[BZOJ4887/Luogu3758][TJOI2017]可乐(动态规划,矩阵快速幂)

发布于 2018-04-08  79 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4887/Luogu3758][TJOI2017]可乐(动态规划,矩阵快速幂)

Description

加里敦星球的人们特别喜欢喝可乐。因而,他们的敌对星球研发出了一个可乐机器人,并且放在了加里敦星球的1号城市上。这个可乐机器人有三种行为: 停在原地,去下一个相邻的城市,自爆。它每一秒都会随机触发一种行为。现 在给加里敦星球城市图,在第0秒时可乐机器人在1号城市,问经过了t秒,可乐机器人的行为方案数是多少?

Tag

动态规划,矩阵快速幂

解决思路

每一次走都是一个类似计数动态规划的过程。发现每一次的转移其实是一样的,所以可以用矩阵快速幂优化转移。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=32;
const int Mod=2017;
const int inf=2147483647;

int n,m;
int Ans[maxN][maxN],Mat[maxN][maxN];
int Backup[maxN][maxN];

void Mul1();
void Mul2();

int main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;//构建转移矩阵
        Mat[u][v]=Mat[v][u]=1;
    }
    for (int i=0;i<=n;i++) Mat[i][i]=Mat[i][0]=1;
    Ans[0][1]=1;//答案矩阵
    int T;cin>>T;
    while (T)//矩阵快速幂
    {
        if (T&1) Mul1();
        Mul2();
        T=T>>1;
    }
    ll sum=0;
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) sum=(sum+Ans[i][j])%Mod;
    cout<<sum<<endl;
    return 0;
}

void Mul1()
{
    for (int i=0;i<=n;i++) Backup[0][i]=Ans[0][i],Ans[0][i]=0;
    for (int i=0;i<=0;i++)
        for (int j=0;j<=n;j++)
            for (int k=0;k<=n;k++)
                Ans[i][j]=(Ans[i][j]+Backup[i][k]*Mat[k][j]%Mod)%Mod;
    return;
}

void Mul2()
{
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) Backup[i][j]=Mat[i][j],Mat[i][j]=0;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            for (int k=0;k<=n;k++)
                Mat[i][j]=(Mat[i][j]+Backup[i][k]*Backup[k][j]%Mod)%Mod;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4887/Luogu3758][TJOI2017]可乐(动态规划,矩阵快速幂)


HNCJ OIer