bzoj4490 随机数生成器Ⅱ加强版

题目链接

题意

给出参数\(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;
}