BZOJ4887 Tjoi2017可乐(动态规划+矩阵快速幂)
2024-10-16 11:37:38
设f[i][j]为第i天到达j号城市的方案数,转移显然,答案即为每天在每个点的方案数之和。矩乘一发即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 33
#define M 110
#define P 2017
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int n,m,k;
struct matrix
{
int n,a[N][N];
matrix operator *(const matrix&b) const
{
matrix c;c.n=n;memset(c.a,,sizeof(c.a));
for (int i=;i<n;i++)
for (int j=;j<b.n;j++)
for (int k=;k<b.n;k++)
c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%P;
return c;
}
}f,v;
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4887.in","r",stdin);
freopen("bzoj4887.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read();
v.n=n+;
for (int i=;i<=m;i++)
{
int x=read(),y=read();
v.a[x][y]=v.a[y][x]=;
}
for (int i=;i<=n;i++) v.a[i][i]=v.a[i][]=;
k=read()+;
f.n=;f.a[][]=;
for (;k;k>>=,v=v*v) if (k&) f=f*v;
cout<<f.a[][];
return ;
}
最新文章
- pdfbox加载pdf时遇到wrappedioexception报错处理方式
- javascript面向对象系列第二篇——创建对象的5种模式
- Modern Operating Systems(Ⅰ)——2014.12.15
- R语言中的logical(0)和numeric(0)以及赋值问题
- eval 与 Function
- HTML 认识
- Visual paradigm Db Archtecture Database config
- python lambda表达式简单用法
- robotframework笔记26
- tyvj1012 P1012 - 火柴棒等式 ——暴力枚举
- 新手浅谈Task异步编程和Thread多线程编程
- Hibernate常见错误整理
- js sleep效果
- 高级I/O之readn和writen函数
- C#对XML、JSON等格式的解析
- Linux中crond服务与crontab用法
- 【Python开发实战】Windows7+VirtualBox+Ubuntu环境配置
- Qt下HBoxLayout里的按钮有重叠
- MySQL系列详解六:MySQL主从复制/半同步演示-技术流ken
- Understanding Docker