蒟阵乘法 get！

A4paper · 2018-08-23 08:21:39 · 个人记录

公式：

A(a,b) * B(b,c) = C(a,c)

即： C(i,j) = Σ(n,k=1) (A(i,k) * B(k,j))

代码实现：

for(int a=1;a<=n;a++)
for(int b=1;b<=n;b++)
for(int c=1;c<=n;c++)
    C[a][c] = A[a][b] * B[b][c];

单位矩阵：

主对角线为 1 ，其他位置为 0 的矩阵。

相当于乘法中的 1 ，

在快速幂中使用单位矩阵可以避免乘 0 的情况

普及：

传送门

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int p = 1000000007;

struct node{
    long long m[3][3];
}x,ans;

long long n;

node mul(node x,node y)
{
    node z;
    memset(z.m,0,sizeof(z.m));
    for(int a=1;a<=2;a++)
    for(int b=1;b<=2;b++)
    for(int c=1;c<=2;c++)
        z.m[a][b] = (z.m[a][b]+(x.m[a][c]*y.m[c][b])%p)%p;
    return z;
}

int main(void)
{
    ios:: sync_with_stdio(false);
    cin >> n;
    if(n == 0)
    {
        cout << "0";
        return 0;
    }
    if(n==1 || n==2)
    {
        cout << "1";
        return 0;
    }
    ans.m[1][1] = ans.m[1][2] = x.m[1][1] = x.m[1][2] = x.m[2][1] = 1;
    x.m[2][2] = 0;
    n -= 2;
    while(n)
    {
        if(n & 1)   ans = mul(ans,x);
        x = mul(x,x);
        n >>= 1;
    }
    cout << ans.m[1][1];
    return 0;
}

提高：

传送门

#include <stdio.h>
#include <iostream>
using namespace std;
const int p = 1000000007;

struct node{
    int m[4][4];
}ans,x;

int T;
int num[155];

# int ml(int a,int b) //快速乘法
{
    int ans = 0;
    while(b)
    {
        if(b & 1)   ans = (ans+a) % p;
        a = (a<<1) % p;
        b >>= 1;
    }
    return ans;
}
node mul(node x, node y)
{
    node z;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
        z.m[i][j] = 0;
    for(int a=1;a<=3;a++)
    for(int b=1;b<=3;b++)
    for(int c=1;c<=3;c++)
        z.m[a][b] = (z.m[a][b]+ml(x.m[a][c],y.m[c][b]) % p) % p;
    return z;
}
int main(void)
{
    scanf("%d",&T);
    for(int i=1;i<=T;i++)   scanf("%d",&num[i]);
    for(int i=1;i<=T;i++)
    {
        ans = (node){{{},{0,1,1,1}}};
        x   = (node){{{},{0,1,0,1},{0,1,0,0},{0,0,1,0}}};
        if(num[i] == 0)
        {
            printf("0\n");  continue;
        }
        if(num[i]>=1 && num[i]<=3)
        {
            printf("1\n");  continue;
        }
        num[i] -= 3;
        //*********************快速幂
        while(num[i])
        {
            if(num[i] & 1)  ans = mul(ans,x);
            x = mul(x,x);
            num[i] >>= 1;
        }
        //*********************
        printf("%d\n",ans.m[1][1]);
    }
    return 0;
}

结合：

传送门

矩阵快速幂 + Floyed

首先，我们需要知道矩阵的一个性质：

对于一个无向图，

设矩阵 A 中用 0 1 表示图的连通性，那么

A 的 x 次幂就会表示出任意一点经过 x 步可到达的点（注意，由于没有自环，一点到它本身是需要两步的）

且权值是可到达的方案数，

如果 A 内存的是边权，那么就可以用 Floyed 跑出两个相差 x 步的点的最短路，

用 A 表示跑了 i 步， B 表示跑了 x - i 步，这样就可以用快速幂了

int n,t,s,e;
int cnt;
int num[MAXN];

struct node{
    int mat[105][105];
}map;

node mul(node a, node b)
{
    node c;
    memset(c.mat,0x3f,sizeof c.mat);
    for(int k=1;k<=cnt;k++)
    for(int i=1;i<=cnt;i++)
    for(int j=1;j<=cnt;j++)
        c.mat[i][j] = min(c.mat[i][j],a.mat[i][k]+b.mat[k][j]);
    return c;
}

int main(void)
{
    memset(map.mat,0x3f,sizeof map.mat);
    cin >> n >> t >> s >> e;
    for(int i=1,w,u,v;i<=t;i++)
    {
        cin >> w >> u >> v;
        if(!num[u]) num[u] = ++cnt;
        if(!num[v]) num[v] = ++cnt;
        map.mat[num[u]][num[v]] = w;
        map.mat[num[v]][num[u]] = w;
    }
    node mak = map;
    n--;
    while(n)
    {
        if(n & 1)   map = mul(map,mak);
        mak = mul(mak,mak);
        n >>= 1;
    }
    cout << map.mat[num[s]][num[e]];
    return 0;
}

巧妙：

传送门

代码不难写，主要是如何建图。

考虑机器人的三种行为：

去下一个城市：就是简单的连边
原地不动：可以看成是自环
爆炸：由于爆炸后机器人就不再行动了，所以可以把所有城市向 0 连边，只进不出，0 与自己连边，这样就保证了爆炸后机器人不会继续移动

int n,m,t,sum;

struct node{
    int mat[MAXN][MAXN];
}a,ans;

node mul(node x, node y)
{
    node ans;
    memset(ans.mat,0,sizeof ans.mat);
    for(int a=0;a<=n;a++)
    for(int b=0;b<=n;b++)
    for(int c=0;c<=n;c++)
        ans.mat[a][c] = (ans.mat[a][c]+x.mat[a][b]*y.mat[b][c])%p;
    return ans;
}

node Fast_mul(node a, int x)
{
    node ans;
    for(int i=1;i<=n;i++) ans.mat[i][i] = 1;
    while(x)
    {
        if(x & 1) ans = mul(ans,a);
        a = mul(a,a);
        x >>= 1;
    }
    return ans;
}

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        a.mat[u][v] = a.mat[v][u] = 1;
    }
    for(int i=0;i<=n;i++)
        a.mat[i][0] = a.mat[i][i] = 1;
    cin >> t;
    node ans;
    memset(ans.mat,0,sizeof ans.mat);
    ans = Fast_mul(a,t);
    for(int i=0;i<=n;i++)
        sum = (sum+ans.mat[1][i])%p;
    cout << sum;
    return 0;
}