\(Sol\)
设\(f_i\)为到第\(i\)秒的方案数,显然\(f_i=\)在第\(i\)秒前爆炸的方案数+在第\(i\)秒爆炸的方案数+在第\(i\)秒停下的方案数+在第\(i\)秒走向下一个城市
的方案数.注意到第四个转移和当前在哪个城市有关,所以要另记一维\(j\)表示当前位置.于是\(f_{i,j}=\)第\(i\)秒前在\(j\)爆炸的方案数+第\(i\)秒在\(j\)爆炸的方案数+第\(i\)秒停在\(j\)的方案数+第\(i\)秒由别的城市走向\(j\)的方案数.记这四个量分别为\(f1,f2,f3,f4\).
\(f1_{i,j}=f1_{i-1,j}+f2_{i-1,j}\)
\(f2_{i,j}=f3_{i-1,j}+f4_{i-1,j}\)
\(f3_{i,j}=f3_{i-1,j}+f4_{i-1,j}\)
\(f4_{i,j}=f3_{i-1,k}+f4_{i-1,k}\),其中,\(k\)是\(j\)的相邻城市.
这样瞎\(dp\)一下就可以获得\(20pts\)的好成绩\(QAQ\).
其实上面的转移方程看起来就很矩阵优化的亚子,于是矩阵优化一下就好辣.
\(Code\)
#include<bits/stdc++.h>
#define il inline
#define Ri register int
#define go(i,a,b) for(Ri i=a;i<=b;++i)
#define yes(i,a,b) for(Ri i=a;i>=b;--i)
#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147483647
using namespace std;
il int read()
{
Ri x=0,y=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*y;
}
const int mod=2017;
int n,m,t,as;
vector<int>to[31];
struct mt
{
int a[121][121];bool ste;
il void clear(){mem(a,0);ste=0;}
}trs,cur;
il void inc(Ri &x,Ri y){x+=y;if(x>=mod)x-=mod;}
il mt operator * (mt x,mt y)
{
mt z;z.clear(),z.ste=x.ste;Ri h=x.ste?1:n*4;
go(i,1,h)
go(j,1,n*4)
go(k,1,n*4)
inc(z.a[i][j],1ll*x.a[i][k]*y.a[k][j]%mod);
return z;
}
il void init()
{
trs.clear();
go(i,1,n)
{
Ri mi=(i-1)*4+1;
trs.a[mi][mi]=trs.a[mi+1][mi]=1;
trs.a[mi+2][mi+1]=trs.a[mi+3][mi+1]=1;
trs.a[mi+2][mi+2]=trs.a[mi+3][mi+2]=1;
go(j,0,(int)to[i].size()-1){Ri k=(to[i][j]-1)*4+3;trs.a[k][mi+3]=trs.a[k+1][mi+3]=1;}
}
}
int main()
{
n=read(),m=read();
go(i,1,m){Ri u=read(),v=read();to[u].push_back(v),to[v].push_back(u);}
init();cur.clear();cur.a[1][3]=1,cur.ste=1;
t=read();
while(t){if(t&1)cur=cur*trs;trs=trs*trs;t>>=1;}
go(i,1,n*4)inc(as,cur.a[1][i]);
printf("%d\n",as);
return 0;
}
随机推荐
-
IBM Bluemix体验：Containers
国际版的Bluemix目前有三个region,US South,United Kingdom和Sydney.其中US South是功能最全的,UK其次,Sydney功能最少.Containers服务在 ...
-
jQuery Mapael – 呈现动态的矢量地图
jQuery Mapael 是基于 Raphael.js 的一个 jQuery 插件,可以显示动态矢量地图.例如,使用 Mapael 可以显示国家能够点击的世界地图.此外,你可以用圈,方形或者图片来标 ...
-
How to Make Terrains in Tiled Map Editor
Published July 13th, 2015 by Stephen Gygi How to Make Terrains in Tiled Map Editor http://www.binary ...
-
c# 路径空格---ProcessStartInfo参数问题
今天在整合程序的时候,要从一个程序转到另一个程序 当然要使用: ProcessStartInfo startInfo = new ProcessStartInfo("\\Program ...
-
myeclipse2015不能启动tomcat，提示： Several ports (8005, 8080, 8009) required by Tomcat v7.0 Server at local
myeclipse2015不能启动tomcat,提示: Several ports (8005, 8080, 8009) required by Tomcat v7.0 Server at local ...
-
Eclipse里的智能提示
Eclipse 3.1里的智能提示功能对于写JAVA程序又不记得类名和函数的人来说是一个很好的助手工具,但是Eclipse里的智能提示的快捷键是Ctrl+Space,在中文Windows操作系统中它确 ...
-
tomcat加载不了spring-webjar终极解决办法
Problems: I included: all Spring libs, Apache Tomcat 7.0 library in Build Path but it still gives er ...
-
如何用VS2010打开VS2012编辑的项目
找到打开项目的开始图标:,右键点击,选择有文本编辑器打开,用下面的语句将文件里面的前两句替换掉.Microsoft Visual Studio Solution File, Format Versi ...
-
java中碰到无法解决的问题：无法访问类的getter访问器
大牛们来看看,俺这是咋了?因博问不让发图,发到这里求助: 以上两个方法都是从mysql中select数据,为嘛第二个出现辣鸡报错? 请注意: reslist.size() = 289 第二种方法已经获 ...
-
MySQL5.6命令笔记
授权root用户在远程终端访问 ' WITH GRANT OPTION;