BZOJ1297 [SCOI2009]迷路 【矩阵优化dp】
2024-08-30 00:51:17
题目
windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
输入格式
第一行包含两个整数，N T。 接下来有 N 行，每行一个长度为 N 的字符串。 第i行第j列为'0'表示从节点i到节点j没有边。 为'1'到'9'表示从节点i到节点j需要耗费的时间。
输出格式
包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。
输入样例
5 30
12045
07105
47805
12024
12345
输出样例
852
提示
30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。 100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。
题解
设\(f[i][t]\)表示\(t\)时刻到达\(i\)号点的方案数
那么有
\[f[i][t] = \sum\limits_{e(j,i) \in edge} f[j][t - e.w]
\]
\]
\(T\)很大，而且显然这是一个齐次式，考虑矩阵优化
但是矩阵优化只能一层层递推，这里边权的限制使我们可能跨多层
发现边权很小，考虑拆点
每个点拆成一长条链，分别管辖各种权值的出边
这样就可以矩阵优化了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 95,maxm = 100005,INF = 1000000000,P = 2009;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct Matrix{
int s[maxn][maxn],n,m;
Matrix(){n = m = 0; memset(s,0,sizeof(s));}
}F,A;
inline Matrix operator *(const Matrix& a,const Matrix& b){
Matrix ans;
if (a.m != b.n) return ans;
ans.n = a.n; ans.m = b.m;
for (int i = 1; i <= ans.n; i++)
for (int j = 1; j <= ans.m; j++)
for (int k = 1; k <= a.m; k++)
ans.s[i][j] = (ans.s[i][j] + a.s[i][k] * b.s[k][j] % P) % P;
return ans;
}
inline Matrix operator ^(Matrix a,int b){
Matrix ans; ans.n = ans.m = a.n;
REP(i,ans.n) ans.s[i][i] = 1;
for (; b; b >>= 1,a = a * a)
if (b & 1) ans = ans * a;
return ans;
}
int n,T;
char s[maxn];
int main(){
n = read(); T = read();
A.n = A.m = 9 * n;
REP(i,n){
scanf("%s",s + 1);
REP(j,n){
if (s[j] != '0'){
int d = s[j] - '0';
A.s[(j - 1) * 9 + 1][(i - 1) * 9 + d] = 1;
}
}
for (int j = 2; j <= 9; j++)
A.s[(i - 1) * 9 + j][(i - 1) * 9 + j - 1] = 1;
}
F.n = 9 * n; F.m = 1;
F.s[1][1] = 1;
Matrix Ans = (A^T) * F;
printf("%d\n",Ans.s[(n - 1) * 9 + 1][1]);
return 0;
}
最新文章
- 不同类型的指针+1之后增加的大小不同(a,&a的地址是一样的，但意思不一样)
- jsp页面直接编写csss
- hdu4283 区间dp
- LPSTR、LPCSTR、LPWSTR、LPCWSTR、LPTSTR、LPCTSTR的来源及意义
- struts----通配符设置
- RabbitMq消息序列化简述
- Flash安全的一些总结
- HTTP笔记1
- x86寄存器总结
- The STM32F746G-DISCO discovery board -- MBED
- Django 模板继承extend 标签include block
- flask celery 使用方法
- Markdown 语法整理大集合2017
- Grunt入门学习之(1) -- 环境安装
- ubuntu创建Centos7镜像&&配置运行环境
- 浅析MySQL主从复制技术（异步复制、同步复制、半同步复制）
- perl6 拖库脚本
- Pythond 读写HDF5文件
- rsync 参数配置说明[转]
- March 7 2017 Week 10 Tuesday