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; }
上一篇: 类的另类用法--数据的封装
推荐阅读
-
洛谷P3600 随机数生成器(期望dp 组合数)
-
bzoj4490 随机数生成器Ⅱ加强版
-
[转]Java中的随机数生成器:Random,ThreadLocalRandom,SecureRandom
-
BZOJ3122: [Sdoi2013]随机数生成器(BSGS)
-
NOI2012 随机数生成器 一道noi水题 error:爆int
-
BZOJ2875 [Noi2012]随机数生成器 【矩阵乘法 + 快速乘】
-
BZOJ 2875 2875: [NOI2012]随机数生成器
-
【NOI2014】随机数生成器___带技巧的枚举+思维
-
BZOJ3671: [Noi2014]随机数生成器(贪心)
-
Linux 文件安全之随机数生成器 李晓辉