zcmimi's blog

查看原题

点击跳转

矩阵加速动态规划统计有多少长度为t的路径

附加条件: 不能走过一条边以后又立刻反着走一次

如果没有附加条件,用邻接矩阵加速即可

那么如何满足这个附加条件呢?

我们设f[i][j]表示第i个时刻在第j条有向边终点的方案数,这样就可以保证不会反着走

然后构建邻接表,枚举点,更新加速矩阵信息

初始矩阵为所有与起始点直接连接的边

答案为所有与结束点连接的边的答案之和

详细可以查看代码

#include<bits/stdc++.h>
typedef long long ll;
const int P=45989;
int n,m,T,A,B,cnt=0,head[55];
struct edge{int to,nxt;}e[121];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
struct mat{
    int a[121][121];
    mat operator*(const mat&x){
        mat c;memset(c.a,0,sizeof c.a);
        for(int k=1;k<=cnt;++k)
            for(int i=1;i<=cnt;++i)
                for(int j=1;j<=cnt;++j)
                    (c.a[i][j]+=1ll*a[i][k]*x.a[k][j]%P)%=P;
        return c;
    }
}a,b;
int neg(int x){return x&1?x+1:x-1;}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&T,&A,&B);
    int x,y,ans=0;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&x,&y),
        add(x+1,y+1),add(y+1,x+1);
    for(int i=1;i<=cnt;++i)
        for(int j=head[e[i].to];j;j=e[j].nxt)
            if(neg(j)!=i)++b.a[i][j];// 构造加速矩阵
    for(int i=head[A+1];i;i=e[i].nxt)++a.a[1][i]; // 构造初始矩阵
    for(--T;T;T>>=1,b=b*b)if(T&1)a=a*b;// 矩阵快速幂
    for(int i=head[B+1];i;i=e[i].nxt)(ans+=a.a[1][neg(i)])%=P; // 统计答案
    printf("%d\n",ans);
}
LG 2151 [SDOI2009]HH去散步
comment评论
Search
search