一本通1647迷路

1647：迷路

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

原题来自：SCOI 2009

Windy 在有向图中迷路了。该有向图有 $N$

现在给出该有向图，你能告诉 Windy 总共有多少种不同的路径吗？

注意：Windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

【输入】

第一行包含两个整数， $N, T$

接下来有 $N$

【输出】

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以 $2009$

【输入样例】

2 2
11
00

【输出样例】

【提示】

样例说明 1

$0 \to 0 \to 1$

样例输入 2

样例输出 2

数据范围与提示：

对于 30% 的数据，满足 $2 \leq N \leq 5, 1 \leq T \leq 30$

对于 100% 的数据，满足 $2 \leq N \leq 10, 1 \leq T \leq 10^{9}$

$2 \leq N \leq 10, 1 \leq T \leq 10^{9}$

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=15;
int n,Time;
int Dis[N][N];
int ans[35][N][N];
int main()
{
    int i,j,k;
    R(n); R(Time);
    for(i=1;i<=n;i++) for(j=1;j<=n;j++)
    {
        char ch=' ';
        while(!isdigit(ch)) ch=getchar();
        Dis[i][j]=ch-'0';
        if(Dis[i][j]) ans[1][i][j]=1;
    }
    for(int t=2;t<=Time;t++)
    {
        for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++)
        {
            ans[t][i][j]+=ans[t-1][i][k]*Dis[k][j];
        }
    }
    Wl(ans[Time][1][n]);
    return 0;
}

（0,1）暴力

对于边权不是0,1的点，似乎一脸生无可恋的样子，因为边权都很小，所以把每个点拆成9个点，表示从 i 点出发走距离1,2，~~，9，

这样就能保证边权为0,1了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const ll Mod=2009;
const int N=95;
int n,Time;
int Dis[N][N];
ll ans[35][N][N];
ll Pic[N][N];
inline void Ad(ll &x,ll y)
{
    x+=y;
    x-=(x>=Mod)?Mod:0;
    return;
}
inline void Build_Pic()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=8;j++) Pic[(i-1)*9+j][(i-1)*9+j+1]=1;
        for(j=1;j<=n;j++) if(Dis[i][j])
        {
            Pic[(i-1)*9+Dis[i][j]][(j-1)*9+1]=1;
        }
    }
    n*=9;
//    for(i=1;i<=n;i++,puts(""))
//    {
//        for(j=1;j<=n;j++) W(Pic[i][j]);
//    }
    return;
}
char S[15];
int main()
{
//    freopen("road.in","r",stdin);
//    freopen("test.out","w",stdout);
    int i,j,k;
    R(n); R(Time);
    for(i=1;i<=n;i++)
    {
        scanf("%s",S+1);
        for(j=1;j<=n;j++) Dis[i][j]=S[j]-'0';
    }
    Build_Pic();
    //暴力
    for(i=1;i<=n;i++) for(j=1;j<=n;j++)
    {
        ans[1][i][j]=Pic[i][j];
    }
    for(int t=2;t<=Time;t++)
    {
        for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++)
        {
            ans[t][i][j]+=ans[t-1][i][k]*Pic[k][j];
            ans[t][i][j]%=Mod;
        }
    }
    Wl(ans[Time][1][n-8]);
    return 0;
}
/*
input
5 30
33454
43629
41539
88547
44006
output
343

input
5 30
12045
07105
47805
12024
12345
output
852
*/

拆边（30pts）

之后加上矩阵快速幂优化就可以潇洒的水过此题了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const ll Mod=2009;
const int N=95;
int n,Time;
int Dis[N][N];
ll ans[N][N],a[N][N],c[N][N];
ll Pic[N][N];
inline void Ad(ll &X,ll Y)
{
    X+=Y;
    X-=(X>=Mod)?Mod:0;
    return;
}
inline void Build_Pic()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=8;j++) Pic[(i-1)*9+j][(i-1)*9+j+1]=1;
        for(j=1;j<=n;j++) if(Dis[i][j])
        {
            Pic[(i-1)*9+Dis[i][j]][(j-1)*9+1]=1;
        }
    }
    n*=9;
//    for(i=1;i<=n;i++,puts(""))
//    {
//        for(j=1;j<=n;j++) W(Pic[i][j]);
//    }
    return;
}
char S[15];
int main()
{
//    freopen("road.in","r",stdin);
//    freopen("my.out","w",stdout);
    int i,j,k;
    R(n); R(Time);
    for(i=1;i<=n;i++)
    {
        scanf("%s",S+1);
        for(j=1;j<=n;j++) Dis[i][j]=S[j]-'0';
    }
    Build_Pic();
    for(i=1;i<=n;i++) ans[i][i]=1;
    memmove(a,Pic,sizeof a);
    int tt=Time;
//    printf("n=%d
",n);
    while(tt)
    {
        if(tt&1)
        {
            memset(c,0,sizeof c);
            for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++)
            {
                Ad(c[i][j],ans[i][k]*a[k][j]%Mod);
            }
            memmove(ans,c,sizeof ans);
        }
        memset(c,0,sizeof c);
        for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++)
        {
            Ad(c[i][j],a[i][k]*a[k][j]%Mod);
        }
        memmove(a,c,sizeof a);
        tt>>=1;
    }
    Wl(ans[1][n-8]);
    return 0;
}
/*
input
2 2
11
00
output
1

input
5 30
33454
43629
41539
88547
44006
output
343

input
5 30
12045
07105
47805
12024
12345
output
852
*/

矩阵快速幂