欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj4490 随机数生成器Ⅱ加强版

程序员文章站 2022-10-06 11:03:17
## 题意 给出参数$C_1,C_2,P$按如下方式生成一个长度为$n \times m$的序列$x$: $x_0 = C_1,x_1=C2$ $x_i=(x_{i-1}+x_{i-1}) \% P \; (i > 1)$ 然后按如下方式生成一个长度为$n \times m$的序列$a$ ......

题目链接

题意

给出参数\(c_1,c_2,p\)按如下方式生成一个长度为\(n \times m\)的序列\(x\):

\(x_0 = c_1,x_1=c2\)

\(x_i=(x_{i-1}+x_{i-1}) \% p \; (i > 1)\)

然后按如下方式生成一个长度为\(n \times m\)的序列\(a\)

\[a_i=\sum\limits_{j=0}^ix_j^2\%p\]

然后现在进行\(q\)次操作,每次操作给出两个参数\(k1,k2\)。表示交换\(k1,k2\)的值。

然后把序列\(a\)按顺序放到一个\(n \times m\)的网格中。

要求出一种方案,使得从\((1,1)\)走到\((n,m)\),所经过的数字排列起来字典序最小。

思路

容易发现,其实就是快速求出\(a_i\)

然后就推一下式子。

\[x_i^2=x_{i-1}^2+2x_{i-1}x_{i-2}+x_{i-2}^2\]
\[x_{i-1}^2=x_i^2-x_{i-2}^2-2x_{i-1}x_{i-2}\]
\[x_{i-1}^2=(x_i+x_{i-2})\times(x_i-x_{i-2}) - 2x_{i-1}x_{i-2}\]
\[x_{i-1}^2=x_{i-1}(x_i+x_{i-2}) - 2x_{i-1}x_{i-2}\]
\[x_{i-1}^2=x_ix_{i-1}+x_{i-1}x_{i-2}-2x_{i-1}x_{i-2}\]
\[x_{i-1}^2=x_ix_{i-1}-x_{i-1}x_{i-2}\]

也就是说

\[x_i^2=x_{i+1}x_i-x_ix_{i-1}\]

这样也就是容易得到

\[a_i=x_{i+1}x_i-c_1(c_2-c_1)\]

所以只要可以快速的求出斐波那契数列第\(i\)项就可以了。

如果直接每次矩阵快速幂会\(tle\)

所以先预处理出\(fbi_1,fbi_2,fbi_3...fbi_m\)\(fbi_m,fbi_{2m},fbi_{3m}...fbi{nm}\)的转移矩阵。

对于第\(i\)行第\(j\)列的数,直接\(o(2^3)\)求出

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
const int n = 500000 + 100,inf = 1e9 + 7;
map<ll,ll>ma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int c1,c2,mod,n,m,q;
namespace fbi {
    struct node {
        int a[3][3],n,m;
        node() {
            memset(a,0,sizeof(a));
        }
        node(int x) {
            n = m = x;
            memset(a,0,sizeof(a));
            for(int i = 1;i <= x;++i) a[i][i] = 1;
        }
        node(int x,int y) {
            n = x,m = y;
            memset(a,0,sizeof(a));
        }
    };
    node operator * (const node &a,const node &b) {
        int n = a.n,m = b.m,k = a.m;
        node ret(n,m);
        for(int k = 1;k <= k;++k) {
            for(int i = 1;i <= n;++i) {
                for(int j = 1;j <= m;++j) {
                    ret.a[i][j] += 1ll * a.a[i][k] * b.a[k][j] % mod;
                    ret.a[i][j] %= mod;
                }
            }
        }
        return ret;
    }
    node fbi(1,2),tmp(2,2),lin[n],row[n];
    void pre() {
        fbi.a[1][1] = c2,fbi.a[1][2] = c1;
        tmp.a[1][1] = tmp.a[1][2] = tmp.a[2][1] = 1;
        
        row[0].n = row[0].m = 2;row[0].a[1][1] = row[0].a[2][2] = 1;
        for(int i = 1;i <= m;++i) row[i] = row[i - 1] * tmp;


        lin[0].n = lin[0].m = 2;
        lin[0].a[1][1] = lin[0].a[2][2] = 1;
        for(int i = 1;i <= n;++i) lin[i] = lin[i - 1] * row[m];
    }
    int solve(ll x) {
        if(x == -1) return (c2 - c1 + mod) % mod;
        if(x == 0) return c1;
        if(x == 1) return c2;
        --x;
        int y = x % m;
        x /= m;
        return (fbi * lin[x] * row[y]).a[1][1];
    }
    int main(ll x) {
        return (1ll * solve(x + 1) * solve(x) % mod - 1ll * c1 * (c2 - c1) % mod + mod) % mod;
    }
}
ll p(ll x,ll y) {
    ll z = (x - 1) * m + y;
    if(ma[z]) return ma[z];
    return z;
}
ll cnt = 1,ans;
void solve(int x,int y) {
    ++cnt;
    if(x == n && y == m) return;
    int down = inf,right = inf;
    if(x != n) down = fbi::main(p(x + 1,y));
    if(y != m) right = fbi::main(p(x,y + 1));
    if(down <= right) {
        ans += cnt * down % mod;
        ans %= mod;
        solve(x + 1,y);
    }
    else {
        ans += cnt * right % mod;
        ans %= mod;
        solve(x,y + 1);
    }
    return;
}
int main() {
    n = read(),m = read(),q = read(),mod = read(),c1 = read(),c2 = read();
    for(int i = 1;i <= q;++i) {
        ll x = read(),y = read(),tx = x,ty = y;
        if(ma[x]) tx = ma[x];
        if(ma[y]) ty = ma[y];
        ma[x] = ty;ma[y] = tx;
    }
    fbi::pre();
    if(ma[1]) ans += fbi::main(ma[1]),ans %= mod;
    else ans += fbi::main(1),ans %= mod;
    solve(1,1);
    cout<<ans;
    return 0;
}