CF852B Neural Network country 题解
题目链接：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;
}
