P5188 PALACINKE 题解

发表于 分类于

考虑以下的经典模型：

给定一张 nn 个点、mm 条边的有向连通图，边权都为 11，求 a,ba,b 两点之间距离为 tt 的路径条数（不可在某一点逗留，n≤25,m≤500,t≤109n\le25,m\le500,t\le10^9）。

tt 很大，自然想到倍增；而 nn 又很小，不妨记矩阵 F(x)\boldsymbol F\left(x\right) 表示答案，其中 Fij(x)\boldsymbol F_{ij}\left(x\right) 代表 t=xt=x 时第 ii 个结点到第 jj 个结点的路径条数。为了实现倍增，思考 F(x)\boldsymbol F\left(x\right) 的递推式：枚举中间节点 kk 得： Fij(x1+x2)=∑k=1nFik(x1)Fkj(x2)\boldsymbol F_{ij}\left(x_1+x_2\right)=\sum_{k=1}^n\boldsymbol F_{ik}\left(x_1\right)\boldsymbol F_{kj}\left(x_2\right)。而这恰好就是矩阵乘法 F(x1+x2)=F(x1)F(x2)\boldsymbol F\left(x_1+x_2\right)=\boldsymbol F\left(x_1\right)\boldsymbol F\left(x_2\right) 的定义，所以答案即为 Fab(t)=[Ft(1)]ab\boldsymbol F_{ab}\left(t\right)=\left[\boldsymbol F^t\left(1\right)\right]_{ab}，而 F(1)\boldsymbol F\left(1\right) 在构图时即可求。于是可以用矩阵快速幂，时间复杂度即为 O(n3log⁡t)O\left(n^3\log t\right)。

本题还需考虑以下细节：

  • 图中存在边权为 22 的边。

    我们可以每条边都新增一个虚拟结点过渡，但是 mm 太大了，最好是将每个结点都配上一个对应的虚拟结点。例如边 i→2ji\overset2\to j 可以拆成 i→1(i+n)→1ji\overset1\to\left(i+n\right)\overset1\to j。

  • 可以回到结点 11 后一直逗留。

    因为结点 1∼2n1\sim2n 已经用过了，可以令结点 (2n+1)\left(2n+1\right) 统计答案。那么只需要新增两条边 1→1(2n+1)1\overset1\to\left(2n+1\right)（新的答案汇入）和 (2n+1)→1(2n+1)\left(2n+1\right)\overset1\to\left(2n+1\right)（旧的答案累加），就得到 F1(2n+1)(t+1)=∑k=0tF11(k)\boldsymbol F_{1\left(2n+1\right)}\left(t+1\right)=\sum_{k=0}^t\boldsymbol F_{11}\left(k\right)。

  • 需要进店买东西。

    如果将每个结点分裂为 24=162^4=16 个结点分别表示每一种状态的话，复杂度将会变为 O(23kn3log⁡t)O\left(2^{3k}n^3\log t\right)（其中 k=4k=4 表示物品数），这显然太大了。若考虑容斥，假设至少购买某单个物品的路径集合分别为 A1,A2,A3,A4A_1,A_2,A_3,A_4， 不购买任意物品的路径集合为 A0A_0，由容斥原理：

    ∣⋂i=14Ai∣=∣⋃i=14Ai‾∣=∑k=14(−1)k∑1≤i1<i2<⋯<ik≤n∣Ai1‾∩Ai2‾∩⋯∩Aik‾∣\left|\bigcap_{i=1}^4A_i\right|=\left|\bigcup_{i=1}^4\overline{A_i}\right|=\sum_{k=1}^4\left(-1\right)^k\sum_{1\le i_1<i_2<\cdots<i_k\le n}\left|\overline{A_{i_1}}\cap \overline{A_{i_2}}\cap\cdots\cap \overline{A_{i_k}}\right|

    此时左边 ∣⋂i=14Ai∣\left|\bigcap_{i=1}^4A_i\right| 即为答案。容易看出 ∣Ai1‾∩Ai2‾∩⋯∩Aik‾∣\left|\overline{A_{i_1}}\cap \overline{A_{i_2}}\cap\cdots\cap \overline{A_{i_k}}\right| 表示 i1,i2,⋯ ,iki_1,i_2,\cdots,i_k 这些物品都不买的方案数，也就是建图时将包含这些物品的边删去即可，时间复杂度降为 O(2kn3log⁡t)O\left(2^k n^3\log t\right)。

    代码中是计算：

    ∣⋂i=14Ai∣=∑k=14(−1)n−k∑1≤i1<i2<⋯<ik≤n∣A0∪Ai1∪Ai2∪⋯∪Aik∣\left|\bigcap_{i=1}^4A_i\right|=\sum_{k=1}^4\left(-1\right)^{n-k}\sum_{1\le i_1<i_2<\cdots<i_k\le n}\left|A_0\cup A_{i_1}\cup A_{i_2}\cup\cdots\cup A_{i_k}\right|

    实际上两个式子是等价的，可以用二项式反演的组合意义证明。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
const int maxm=505;
const int maxn=55;
const int P=5557;
int N,M,T,Ans,L[maxm],R[maxm],X[maxm];
struct graph{
    int n,ans[maxn][maxn];
    graph(){clear();}
    void setNodeNumber(int n_){n=n_;}
    void addEdge(int l,int r){ans[l][r]=(ans[l][r]+1)%P;}
    void init(int n_){setNodeNumber(n_);for(int i=1;i<=n;i++)ans[i][i]=1;}
    void clear(){n=0;memset(ans,0x00,sizeof ans);}
    void operator*=(const graph B){
        graph C;C.n=n;
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            C.ans[i][j]=(C.ans[i][j]+ans[i][k]*B.ans[k][j]%P)%P;
        *this=C;
    }
    void operator^=(const int B){
        graph w=*this,ret;ret.init(n);
        for(int k=B;k;k>>=1){if(k&1) ret*=w;w*=w;}
        *this=ret;
    }
    int getAns(int s,int t){return ans[s][t];}
}Map;
int read(){
    int f=1,ret=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f; ch=getchar();}
    while( isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return f*ret;
}
int countTrueBinary(int x){
    int ret=0;
    for(int k=0;k<0x20;k++) if(x&1<<k) ret++;
    return ret;
} 
int main(){
    N=read(),M=read();
    for(int i=1;i<=M;i++){
        L[i]=read(),R[i]=read();string s;cin>>s;
        for(int j=0;j<s.size();j++) switch(s[j]){
            case'B':X[i]|=0x08;break;
            case'J':X[i]|=0x04;break;
            case'M':X[i]|=0x02;break;
            case'P':X[i]|=0x01;break;
        }
    }
    T=read();
    for(int k=0;k<0x10;k++){
        Map.clear();
        Map.setNodeNumber(N<<1|1);
        Map.addEdge(     1,N<<1|1);
        Map.addEdge(N<<1|1,N<<1|1);
        for(int i=1;i<=N;i++) Map.addEdge(i,i+N);
        for(int i=1;i<=M;i++) Map.addEdge(L[i],R[i]);
        for(int i=1;i<=M;i++) if((X[i]&k)==X[i]) Map.addEdge(L[i]+N,R[i]);
        Map^=T+1;
        if(countTrueBinary(k)&1) Ans=((Ans-Map.getAns(1,N<<1|1))%P+P)%P;
        else                     Ans= (Ans+Map.getAns(1,N<<1|1))%P     ;
    }
    printf("%d\n",Ans);
    return 0;
}