目录
显示
题目链接
https://www.luogu.org/problem/P4159
题解
我们将一个点 i 拆分成 9 个点,设这九个点的编号为 9*i+1 \ldots 9*i+9。我们先从左到右给这九个点顺次连边。
如果原图中 i 和 j 之间有一条权值为 k 的边,我们就在新图中从 9*i+k 向 9*j+1 连一条边。
这么连边的意义是很明显的:我们发现从 i 号点到 j 号点刚好走了 k 条边。
剩下就是求邻接矩阵的幂了。可以参考 [TJOI2017]可乐 一题。
#include <iostream>
#include <cstring>
#define MOD 2009
using namespace std;
struct mat
{
int a[105][105];
mat()
{
memset(a,0,sizeof(a));
}
}f;
long long n,t;
char s[15];
mat operator*(mat a,mat b)
{
mat ans;
for(int k=1;k<=n*9+1;k++)
for(int i=1;i<=n*9+1;i++)
for(int j=1;j<=n*9+1;j++)
ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%MOD;
return ans;
}
mat fpow(mat x,long long y)
{
mat ans;
for(int i=1;i<=n*9+1;i++)
ans.a[i][i]=1;
while(y)
{
if(y&1)ans=ans*x;
x=x*x;
y>>=1;
}
return ans;
}
int main()
{
cin>>n>>t;
for(int i=0;i<n;i++)
{
cin>>s;
for(int j=i*9+1;j<=i*9+8;j++)
f.a[j][j+1]=1;
for(int j=0;j<n;j++)
if(s[j]-='0')
f.a[i*9+s[j]][j*9+1]=1;
}
cout<<fpow(f,t).a[1][(n-1)*9+1]<<endl;
return 0;
}
#include <iostream>
#include <cstring>
#define MOD 2009
using namespace std;
struct mat
{
int a[105][105];
mat()
{
memset(a,0,sizeof(a));
}
}f;
long long n,t;
char s[15];
mat operator*(mat a,mat b)
{
mat ans;
for(int k=1;k<=n*9+1;k++)
for(int i=1;i<=n*9+1;i++)
for(int j=1;j<=n*9+1;j++)
ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%MOD;
return ans;
}
mat fpow(mat x,long long y)
{
mat ans;
for(int i=1;i<=n*9+1;i++)
ans.a[i][i]=1;
while(y)
{
if(y&1)ans=ans*x;
x=x*x;
y>>=1;
}
return ans;
}
int main()
{
cin>>n>>t;
for(int i=0;i<n;i++)
{
cin>>s;
for(int j=i*9+1;j<=i*9+8;j++)
f.a[j][j+1]=1;
for(int j=0;j<n;j++)
if(s[j]-='0')
f.a[i*9+s[j]][j*9+1]=1;
}
cout<<fpow(f,t).a[1][(n-1)*9+1]<<endl;
return 0;
}
#include <iostream> #include <cstring> #define MOD 2009 using namespace std; struct mat { int a[105][105]; mat() { memset(a,0,sizeof(a)); } }f; long long n,t; char s[15]; mat operator*(mat a,mat b) { mat ans; for(int k=1;k<=n*9+1;k++) for(int i=1;i<=n*9+1;i++) for(int j=1;j<=n*9+1;j++) ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%MOD; return ans; } mat fpow(mat x,long long y) { mat ans; for(int i=1;i<=n*9+1;i++) ans.a[i][i]=1; while(y) { if(y&1)ans=ans*x; x=x*x; y>>=1; } return ans; } int main() { cin>>n>>t; for(int i=0;i<n;i++) { cin>>s; for(int j=i*9+1;j<=i*9+8;j++) f.a[j][j+1]=1; for(int j=0;j<n;j++) if(s[j]-='0') f.a[i*9+s[j]][j*9+1]=1; } cout<<fpow(f,t).a[1][(n-1)*9+1]<<endl; return 0; }