矩阵乘法 NOI2012的一道题

今天，[kzj](https://www.cnblogs.com/kzj-pwq/)大佬教了我矩阵加速。

让我以这篇随笔表示感谢吧！

这是我刷的一道题：NOI2012 随机数据生成器。

就是普通的矩阵加速，只是要注意的是：

直接用乘法会爆long long，可以参考一下 黑科技 慢速乘。

可以把乘法转换成加法，很好取模。

贴上丑陋的代码吧～忽略函数名

#include <bits/stdc++.h>

using namespace std;

typedef long long ull;

const ull A=0;

ull m,a,c,x0,n,g;

ull f[3],t[3][3]={

{0,0,0},

{0,A,0},

{0,1,1}

};

ull suan(ull x,ull y)

{

    ull ans=0;

    while (y) {

        if (y&1)

            ans=((ans%m)+(x%m))%m;

        x=((x%m)+(x%m))%m;

        y>>=1;

    }

    return ans;

}

ull fuyan()

{

    ull d[3];

    memcpy(d,f,sizeof(d));

    memset(f,0,sizeof(f));

    for (int i=1;i<=2;++i)

        for (int j=1;j<=2;++j)

            f[i]=(f[i]%m+suan(d[j]%m,t[j][i]%m))%m;

}

ull yuzhouzhou()

{

    ull d[3][3];

    memcpy(d,t,sizeof(d));

    memset(t,0,sizeof(t));

    for (int i=1;i<=2;++i)

        for (int j=1;j<=2;++j)

            for (int k=1;k<=2;++k)

                t[i][j]=(t[i][j]%m+suan(d[i][k]%m,d[k][j]%m))%m;

}

ull work(ull p)

{

    while (p) {

        if (p&1)

            fuyan();

        yuzhouzhou();

        p>>=1;

    }

    return f[1];

}

int main()

{

    cin>>m>>a>>c>>x0>>n>>g;

    t[1][1]=a%m;

    f[1]=x0;f[2]=c;

    cout<<work(n)%g<<"\n";

    return 0;

}

巴特西

矩阵乘法 NOI2012的一道题

最新文章

热门文章