当前位置: 代码迷 >> 综合 >> BZOJ 4887 [Tjoi2017] 可乐
  详细解决方案

BZOJ 4887 [Tjoi2017] 可乐

热度:27   发布时间:2024-01-19 01:57:13.0

Description

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

Input

第一行输入两个正整数 N,M N,M, N N表示城市个数, M M表示道路个数。( 1≤N≤30 1≤N≤30, 0≤M≤100 0≤M≤100)

接下来M行输入 u,v u,v,表示 u,v u,v之间有一条道路。( 1≤u,v≤n 1≤u,v≤n)保证两座城市之间只有一条路相连。

最后输入时间 t t。

Output

输出可乐机器人的行为方案数,答案可能很大,请输出对 2017 2017取模后的结果。

Sample Input

3 2
1 2
2 3
2

Sample Output

8

HINT

对于20%的数据,有 1<t≤1000 1<t≤1000
对于100%的数据,有 1<t≤106 1<t≤106。

Source

TJOI2017 D1T1

~~~~~~~~~~~~~~~~~~~~~~~~~~~

矩阵快速幂优化DP~

用f[i][j][0/1]表示在i时刻,j点,1不爆炸,0已爆炸的方案数,那么f[i][j][0]=f[i-1][j][0]+f[i-1][j][1],f[i][j][1]=f[i-1][j][1]+f[i-1][k][1](其中k表示与j相邻的点)。

然后,就T了QAQ

所以我们需要一些优化。

先看f[i][j][1]=f[i-1][j][1]+f[i-1][k][1],如果我们假设i与自己相连,那么这个式子就是f[i][j][1]=f[i-1][k][1],可以用矩阵快速幂来计算——

我们在a矩阵中记录图的联通性(注意这里a[i][i]=1),然后自乘t次,再与f[0][i][1]相乘即为答案。

然后,f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]等价于sum{f[i-1][j][1]},由前面f[i][j][1]的求法可知它是个等比数列,求和公式一套就好了~

程序里面的f和g数组是学的Xiejiadong神犇的,相当于求矩阵的和,并没有DP的意思,这里可能容易混。

我在函数里面把v写成了y……所以一定要检查有没有变量用错的情况啊,尤其是u和v和y!


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define mod 2017int n,m,t,x,y,f[31],g[31],ans;struct node{int a[31][31];
}a,b;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}node operator + (node u,node v)
{node z;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) z.a[i][j]=u.a[i][j]+v.a[i][j]%mod;return z;
}node operator * (node u,node v)
{node z;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){z.a[i][j]=0;for(int k=1;k<=n;k++) z.a[i][j]=(z.a[i][j]+u.a[i][k]*v.a[k][j]%mod)%mod;}return z;
}node mi(node u,int v)
{node z;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) z.a[i][j]=i==j ? 1:0;for(;v;v>>=1,u=u*u) if(v&1) z=z*u;return z;
}node sum(node u,int v)
{node z;memset(z.a,0,sizeof(z.a));if(!v) return z;if(v==1) return u;for(int i=1;i<=n;i++) z.a[i][i]=1;z=z+mi(u,v>>1);z=z*(sum(u,v>>1));if(v&1) z=z+mi(u,v);return z;
}int main()
{n=read();m=read();for(int i=1;i<=m;i++) x=read(),y=read(),a.a[x][y]=a.a[y][x]=1;for(int i=1;i<=n;i++) a.a[i][i]=1;t=read();b=a;a=mi(a,t);g[1]=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) f[i]=(f[i]+g[j]*a.a[i][j]%mod)%mod;for(int i=1;i<=n;i++) ans=(ans+f[i])%mod;b=sum(b,t-1);for(int i=1;i<=n;i++) b.a[i][i]=(b.a[i][i]+1)%mod;memset(f,0,sizeof(f));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) f[i]=(f[i]+g[j]*b.a[i][j]%mod)%mod;for(int i=1;i<=n;i++) ans=(ans+f[i])%mod;printf("%d\n",ans);return 0;
}