TJOI2017 可乐

wjh15101051's space

卧薪尝胆，厚积薄发。

TJOI2017 可乐

Date: Fri Sep 07 21:02:16 CST 2018

In Category: NoCategory

Description：

一个机器人每时刻有三种行为：停留，走到图上相邻的城市，自爆，问行为方案数。

$1\le n \le 30,1\le m \le 100,1\le time\le 10^6$

Solution：

新建一个 $n+1$ 代表自爆，连一个自环，这样自爆后对答案的贡献只能是一，停留也连一个自环，在邻接矩阵上做矩阵快速幂即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,t;

#define MAXN 50

#define MOD 2017

struct matrix

{

	int m[MAXN][MAXN];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= n;++i)

			for(int j = 1;j <= n;++j)

				for(int k = 1;k <= n;++k)

					c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;

		return c;

	}

	friend matrix operator ^ (matrix a,int b)

	{

		matrix res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}g;

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		g.m[a][b] = g.m[b][a] = 1;

	}

	scanf("%d",&t);

	for(int i = 1;i <= n;++i)g.m[i][n + 1] = 1;

	++n;

	for(int i = 1;i <= n;++i)g.m[i][i] = 1;

	g = g ^ t;

	int ans = 0;

	for(int i = 1;i <= n;++i)ans = (ans + g.m[1][i]) % MOD;

	cout << ans << endl;

	return 0;

}

In tag: DP-矩阵加速

wjh15101051