P6841

· · 题解

Solution

有趣的题目 . 建议评分 : 紫 .

考虑把每个字母看做一个点 , 距离看做边 , 那么就相当于在有向图上找长度不超过 N 的路径 .

好像比较难 , 先来看几个简单问题 .

问题 1

给你一个图 , 节点数 n \le 100 , 求任意两点间经过 m(m \le 10^{18}) 条边的方案数 .

我会 DP ! dp_{i,j,k} 表示从 i 到 j 经过 k 条边的方案数 . 转移方程 : dp_{i,j,k}=\sum dp_{i,v,k-1} , (v,j) \in E .

根据经验 , 如果一个 DP 朴素写法只改变一个维度 , 这个维度只与上一个有关系 , 那么可以矩阵加速 .

尝试构造转移矩阵 , 把第 k 条边的情况向第 k+1 条转移 , 发现这个矩阵就是图的邻接矩阵 !

初始矩阵应为单位矩阵 (dp_{i,i,0}=1) , 所以答案矩阵就是邻接矩阵的 m 次幂 ! 矩阵快速幂解决 .

问题 2

给你一个图 , 节点数 n \le 50 , 每条边的边权不超过 5 , 求任意两点间经过权值和为 m(m \le 10^{18}) 的边互相到达的方案数 .

和上一个问题很相似 , 可惜上一个算法不再使用 . 考虑拆点 , 给每一个点 4 个附属点 . 这 5 个点排成一条链 .

如果 u 到v 的边权为 k , 那么就在 u 的第 k 个点向 v 连边 . 这样从 u 到 v 就经过 k 条边 . 这时就和上一个问题一样了 .

然后回归本题 . 用问题 2 中的算法可以解决长度为 N 的路径数 . 那么长度小于 N 怎么办呢 ? 想办法补一些点让它变成 N ! 那么避免重复 , 就加在最前面 .

我们可以创建一个虚点 , 向自己和其它字母的主点连边 , 这样找从虚点到主点长度为 N+1 的路径 , 就一定是在虚点停留若干长度后 , 从一个点到另一个点 . 这样就可以找到长度小于 N 的路径了 !

练习题 :

P4159 [SCOI2009] 迷路

P2886 [USACO07NOV] Cow Relays G

P3758 [TJOI2017] 可乐

code :

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200+10,MOD=1e9+7;
struct Matrix {
    int n,m,val[MAXN][MAXN];
    void init(int N,int M) {
        return n=N,m=M,memset(val,0,sizeof(val)),void();
    }
    void output(void) {
        printf("Matrix Output:\n%lld %lld\n",n,m);
        ffor(i,1,n) {
            ffor(j,1,m) printf("%lld ",val[i][j]);
            printf("\n");
        }
        return ;
    }
};
Matrix unit_matrix(int n) {
    Matrix res;
    res.init(n,n);
    ffor(i,1,n) res.val[i][i]=1;
    return res;
}
Matrix operator *(Matrix A,Matrix B) {
    Matrix res;
    int p=A.n,q=A.m,r=B.m;
    res.init(p,r);
    ffor(k,1,q) ffor(i,1,p) ffor(j,1,r) res.val[i][j]+=A.val[i][k]*B.val[k][j],res.val[i][j]%=MOD;
    return res;
} 
Matrix operator ^(Matrix A,int p) {
    Matrix base=A,res=unit_matrix(A.n);
    while(p) {
        if(p&1) res=res*base;
        base=base*base,p>>=1;
    }
    return res;
}
int n,m;
signed main() {
    Matrix A;
    A.init(5*26+1,5*26+1);
    cin>>n>>m;
    ffor(i,1,26) A.val[i][i+26]=A.val[i+26][i+26*2]=A.val[i+26*2][i+26*3]=A.val[i+26*3][i+26*4]=1;
    ffor(i,1,26) ffor(j,1,26) A.val[i][j]=A.val[j][i]=1;
    ffor(i,1,m) {
        char ch1,ch2;int len;
        cin>>ch1>>ch2>>len;
        A.val[ch1-'a'+1][ch2-'a'+1]=A.val[ch2-'a'+1][ch1-'a'+1]=0;
        A.val[ch1-'a'+1+26*(len-1)][ch2-'a'+1]=1,A.val[ch2-'a'+1+26*(len-1)][ch1-'a'+1]=1;
    }
    ffor(i,1,26) A.val[131][i]=1;
    A.val[131][131]=1,A=A^(n+1);
    int ans=0;
    ffor(i,1,26) ans+=A.val[131][i],ans%=MOD;
    cout<<ans;
    return 0;
}