bzoj1875: [SDOI2009]HH去散步

终于A了。。。早上按自己以前的写法一直WA。下午换了一种写法就A了qwq

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
const int mod=45989;
const int nmax=25;
const int maxn=125;

int N,M,T,A,B;
int U[maxn],V[maxn],id[maxn],f[maxn];
struct matrix{
	int a[maxn][maxn];
	matrix(){
		clr(a,0);
	}
	matrix operator*(const matrix &o)const {
	    matrix rhs;
	    REP(i,1,M) REP(j,1,M) REP(k,1,M) rhs.a[i][j]=(rhs.a[i][j]+a[i][k]*o.a[k][j])%mod;
	    return rhs;
	}
}a,b;

int main(){
	N=read(),M=read(),T=read(),A=read(),B=read();T--;
	REP(i,1,M){
		U[i]=read(),V[i]=read();U[i+M]=V[i],V[i+M]=U[i];id[i]=id[i+M]=i;
	}
	
	M*=2;
	REP(i,1,M) REP(j,1,M) if(id[i]!=id[j]&&V[i]==U[j])  b.a[i][j]=1;
	REP(i,1,M) a.a[i][i]=1;
	while(T) {
		if(T&1) a=a*b;
		b=b*b;T>>=1;
	}
	
	REP(i,1,M) if(U[i]==A) f[i]=1;
	int ans=0;
	REP(i,1,M) if(V[i]==B) 
	  REP(j,1,M) ans=(ans+a.a[j][i]*f[j])%mod;
	printf("%d
",ans);
	return 0;
}

1875: [SDOI2009]HH去散步

Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1300 Solved: 610
[Submit][Status][Discuss]

Description

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径

Input

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但不保证任意两个路口之间至多只有一条路相连接。路口编号从0到N − 1。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模45989。

Output

一行，表示答案。

Sample Input

4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

Sample Output

HINT

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Source

Day1

[Submit][Status][Discuss]