CF852B Neural Network country 题解

题意：

给定一个包含一个出发点 $s$ ，终止点 $t$ 以及 $L$ 层 $V_1,V_2,\dots,V_L$ ，每层都包含 $N$ 个顶点的带边权有向分层图。从出发点 $s$ 到第一层 $V_1$ 中每个顶点都有一条带权边，从最后一层 $V_L$ 到终止点 $t$ 中每个顶点也都有一条带权边。对于所有 $1\le i<L$ ，第 $i$ 层的每个顶点到第 $i+1$ 层中的每个顶点都会连有一条带权有向边，且第 $i$ 层的每个顶点连出的边权完全相同，并且任意相邻两层之间所连边权完全相同。可以参照样例解释中链接内图示结合样例帮助理解。

现给出该分层图，你需要计算有多少种从 $s$ 走到 $t$ 的路径，使得路径上经过边权值和能被 $M$ 整除？由于答案可能过大，你需要将答案对 $10^9+7$ 取模后输出。

对于 $100\%$ 的数据，$1\le N\le 10^5,~2\le L\le 10^5,~2\le M\le 50,~0\le a_i,b_i,c_i<M$

~~感谢Roundgod老师的耐心指导，我还是太蠢了QAQ~~

这道题其实就是给了一个有特殊性质的分层图

然后用了 $s$ 和 $t$ 连上这个分层图

这个分层图的特殊性质就是

每个上一层的结点 $u_i$ 到下一层的结点 $v_i$ ，边权只由 $v_i$ 决定

因此对于分层图里面同一层的点，我们可以看作同一个点

每个点和下一层的点都有 $n$ 中走法，也就对应了路径和的 $O(n)$ 种变化

这种题的常见思路就是，算出不同路径和的答案

然后把能被 $M$ 整除的答案加上，就是最终答案

仔细思考一下，我们有没有必要记录整个路径和？

注意到 $M \le 50$ ，这说明路径和模 $M$ 的剩余系很小

而一条路径的边权和能否被 $M$ 整除，就等价于模 $M$ 等于 $0$

这样我们就可以很容易的设出dp状态了

这里我们只算分层图上的 $1\sim L-1$ 层，因为第 $L$ 层显然不满足特殊性质

因为第 $L$ 层每个点到 $t$ 的边权不同，我们要单独处理。

设 $f_{i,j}$ 表示走到分层图上的第 $i$ 层，从第一层出发，边权和模 $M$ 为 $j$ 的方案数

转移方程就是

$f_{i,j}=\sum_{0\le k < M} f_{i-1,k} \times A_{k,j}$

其中 $A_{k,j}$ 表示存在 $k$ 向 $j$ 的转移，这个可以预处理出来

稍微整理一下，可得

$f^{i}_j = \sum _{0 \le k < M} f^{i-1}_{k} \times A_{k,j}$

可以发现这个柿子就是矩阵乘法的定义，只不过 $f$ 是个 $1 \times M$ 的矩阵

于是写成矩阵乘法的形式，就是

$f^k = f^{k-1} \times A = f^{k-2} \times A^2 = A^k$

考虑矩阵快速幂计算

实际上的答案是 $A \times B^{L-2} \times C$（和上面写的稍微有些区别）

分别对应 $s \to V_1,V_1 \to V_{L-1},V_{L-1}\to t$

时间复杂度 $O(M^3 \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)
const int mod=1e9+7;
typedef vector<int> vec;
typedef vector<vec> mat;
void add(int &x,int y){x+=y%mod; if(x>=mod)x-=mod;}
mat mul(mat &A,mat &B)
{
    int n=A.size(),m=A[0].size(),p=B[0].size();
    mat C(n,vec(p));
    for(int k=0; k<m; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<p; j++)
                add(C[i][j],A[i][k]*B[k][j]%mod);
    return C;
}
mat qpow(mat A,int k)
{
    int n=A.size(); 
    mat B(n,vec(n));
    for(int i=0; i<n; i++) B[i][i]=1;
    while(k)
    {
        if(k&1) B=mul(B,A);
        A=mul(A,A); k>>=1;
    }
    return B;
}
void print(mat &A)
{
    int n=A.size(),m=A[0].size();
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cout << A[i][j] << " \n"[j==m-1];
}
int n,m,l,a[N],b[N],c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> l >> m;
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) cin >> b[i];
    for(int i=0; i<n; i++) cin >> c[i];
    mat A(m,vec(m)),B(m,vec(m)),C(m,vec(m));
    for(int i=0; i<n; i++) ++A[0][a[i]%m];
    for(int i=1; i<m; i++)
        for(int j=0; j<m; j++)
            A[i][j]=A[0][(j-i+m)%m];
    for(int i=0; i<n; i++) ++C[0][(c[i]+b[i])%m];
    for(int i=1; i<m; i++)
        for(int j=0; j<m; j++)
            C[i][j]=C[0][(j-i+m)%m];
    for(int i=0; i<n; i++) ++ B[0][b[i]%m];
    for(int i=1; i<m; i++)
        for(int j=0; j<m; j++)
            B[i][j]=B[0][(j-i+m)%m];
    B=qpow(B,l-2); A=mul(A,B); A=mul(A,C);
    cout << A[0][0] << '\n';
    return 0;
}