题目链接

题意

给出参数(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=sumlimits_{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; }