WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 5437: 迂回
BZOJ 5437: 迂回

Description

给定一有向图,边长均为1,求长度小于k的环的个数mod~m
保证有向图中无自环(即g[i,i]=’N’)。
什么样的环属于不同的解,详见样例解释。

Input

第一行n表示节点个数
接下来n行长度为n的字符串,g[i,j]=’Y’表示ij有一条边,g[i,j]=’N’反之。
最后一行两个整数k,m
n \leq 100, k \leq 10^6, m \leq 10^9

Output

一个整数表示答案.

Sample Input

4
NYNY
NNYN
YNNN
YNNN
6 100

Sample Output

12

样例解释

12个解分别为:(0,3) ; (3,0) ; (0,1,2) ; (1,2,0) ; (2,0,1);(0,3,0,3) ; (3,0,3,0) ; (0,1,2,0,3) ; (0,3,0,1,2) ; (1,2,0,3,0) ; (2,0,3,0,1) ; (3,0,1,2,0)。

题解

假设邻接矩阵为Edge,如果要求刚好走K步,走成一个环的方案数。我们只需要使用快速幂+矩阵乘法,求出走刚好K步的邻接矩阵Matrix_k=Edge^k,然后求和对角线就可以了。

但是,这题要求走不多于K步走成环的方案数,所以,我们需要求的是\sum_{i=0}^k Matrix_i的对角线之和。我们令Ans_k=\sum_{i=0}^k Matrix_i,然后去考虑矩阵乘法的某一个中间过程,比如用Ans_kEdge^{2^p}相乘:

\begin{aligned}
Ans_k\times Edge^{2^p} &= \sum_{i=0}^{k}Matrix_i\times Edge^{2^p}\\
&= \sum_{i=2^p+1}^{k+2^p} Matrix_i \\
&= \sum_{i=0}^{k+2^p} Matrix_i -\sum_{i=0}^{2^p} Matrix_i\\
&= Ans_{k+2^p}-Ans_{2^p}
\end{aligned}

所以,如果我们可以知道所有的Ans_{2^p},就可以用类似快速幂计算出所有答案了。
Ans_{2^p}的答案是很好计算的,我们可以倍增进行计算:

\begin{aligned}
Ans_{2^p} &= \sum_{i=2^{p-1}+1}^{2^p} Matrix_i + \sum_{i=0}^{2^{p-1}} Matrix_i\\
&= Ans_{2^{p-1}}\times Edge^{2^{p-1}}+Ans_{2^{p-1}}
\end{aligned}

代码

/**
* Author : WNJXYK
* Date : 20180824
* Problem : 5437
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const int MAXN=1e2+10;

int MOD=998244353;
struct Matrix{
    int n, m;
    int v[MAXN][MAXN];
    Matrix(){}
    Matrix(int n0, int m0):n(n0), m(m0){memset(v, 0, sizeof(v));}
    inline void set(int i, int j, LL v0){ v[i][j]=v0; }
    inline void E(){
        assert(n==m);
        memset(v, 0, sizeof(v));
        for (int i=0; i<n; i++) v[i][i]=1;
    }
    Matrix operator * (const Matrix &b){
        assert(m==b.n);
        Matrix ret=Matrix(n, b.m);
        for (int i=0; i<n; i++){
            for (int j=0; j<b.m; j++){
                for (int k=0; k<m; k++){
                    ret.v[i][j]=(1LL*v[i][k]*b.v[k][j]%MOD+ret.v[i][j])%MOD;
                }
            }
        }
        return ret;
    }

    Matrix operator + (const Matrix &b){
        assert(n==b.n && m==b.m);
        Matrix ret=Matrix(n, m);
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                ret.v[i][j]=(v[i][j]+b.v[i][j])%MOD;
            }
        }
        return ret;
    }

    inline void Print(){
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                printf("%d ", v[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
};

inline int read(){
    char x=getchar();
    while(!(x=='N' || x=='Y')) x=getchar();
    return (x=='Y'?1:0);
}

Matrix bin[25], rate[25], ans;

inline void solve(int n, int T){
    Matrix edge=Matrix(n, n);
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) edge.set(i, j, read());
    int K, SK=1; scanf("%d%d", &K, &MOD); --K;

    rate[0]=edge, bin[0]=edge;
    for (int i=1; i<=20; i++){
        bin[i]=bin[i-1]*bin[i-1];
        rate[i]=rate[i-1]*bin[i-1]+rate[i-1];
    }

    Matrix ret=edge; K--;
    for (int i=0; i<=20 && K; i++, K>>=1){
        if (K&1) ret=ret*bin[i]+rate[i];
    }

    int ans=0;
    for (int i=0; i<n; i++) ans=(ans+ret.v[i][i])%MOD;
    printf("%d\n", ans);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    int n, cas=0;
    while(scanf("%d", &n)!=EOF) solve(n, ++cas);
    return 0;
}


赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 5437: 迂回
Description 给定一有向图,边长均为$1$,求长度小于$k$的环的个数$mod~m$。 保证有向图中无自环(即$g[i,i]='N'$)。 什么样的环属于不同的解,详见样例解释。 Input 第一行$n$表示节点…
扫描二维码继续阅读
2018-08-24
<--! http2https -->