题目链接
题意
给出参数(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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604657.html