【[SCOI2009]迷路】
2024-09-21 12:56:19
大水题一遍
过掉比较繁琐的拆点还是非常开心的
发现每一条边的边权可能不是\(1\),但是边权的范围非常小,同时点数也非常小,只有\(n<=10\),所以我们可以将一个点拆成九个点,之后随便一连边就跑过去了
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define maxn 105
#define LL long long
const int mod=2009;
int a[maxn][maxn],ans[maxn][maxn];
int sz;
inline void did_a()
{
int mid[maxn][maxn];
for(re int i=1;i<=sz;i++)
for(re int j=1;j<=sz;j++)
mid[i][j]=a[i][j],a[i][j]=0;
for(re int k=1;k<=sz;k++)
for(re int i=1;i<=sz;i++)
for(re int j=1;j<=sz;j++)
a[i][j]=(a[i][j]+mid[i][k]*mid[k][j])%mod;
}
inline void did_ans()
{
int mid[maxn][maxn];
for(re int i=1;i<=sz;i++)
for(re int j=1;j<=sz;j++)
mid[i][j]=ans[i][j],ans[i][j]=0;
for(re int k=1;k<=sz;k++)
for(re int i=1;i<=sz;i++)
for(re int j=1;j<=sz;j++)
ans[i][j]=(ans[i][j]+mid[i][k]*a[k][j])%mod;
}
inline void quick(LL b)
{
while(b)
{
if(b&1ll) did_ans();
b>>=1ll;
did_a();
}
}
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
int n;
LL m;
char S[maxn];
int main()
{
n=read(),m=read();
sz=n*10;
for(re int i=1;i<=n;i++)
{
int now=(i-1)*10;
for(re int j=2;j<=9;j++)
a[j+now-1][j+now]=1;
}
for(re int i=1;i<=n;i++)
{
scanf("%s",S+1);
int now=(i-1)*10;
for(re int j=1;j<=n;j++)
{
if(S[j]=='0') continue;
int to=S[j]-48;
a[now+9][(j-1)*10+10-to]=1;
}
}
for(re int i=1;i<=sz;i++)
ans[i][i]=1;
quick(m);
printf("%d\n",ans[9][(n-1)*10+9]);
return 0;
}
最新文章
- Request 请求页面的地址路径获取
- css/js(工作中遇到的问题)
- nginx 做负载均衡
- RDLC系列之五 初试XAML
- Tutorial: Analyzing sales data from Excel and an OData feed
- css3 :nth-child 常用用法
- 初识 istringstream、ostringstream、stringstream 运用
- dsu + lca
- Android WebView 开发详解(二)
- 纯 CSS 创建各种不同的图形形状
- Response.Expires 属性 (转载于疯狂客的BLOG)
- Longest Consecutive Sequence 解答
- poj 1149 pigs ---- 最大流
- Linear Regression(线性回归)(三)—代价函数J(θ)选择的概率解释
- 深入剖析Tomcat类加载机制
- iP私网地址
- MySql笔记一:安装MySql
- 信息收集之censys
- Xcode 快捷键及代码格式化
- Go开发环境与LIteIDE安装、配置、搭建