本文共 1521 字,大约阅读时间需要 5 分钟。
题解:
由于x,y,z 都是大于等于1 的,
所以原序列是升序的,但是注意给你的a[0],a[1]可能不是升序的(这里要特别处理)。 对于这些操作很容易发现较长的操作会覆盖掉较小的操作 所以如果一个操作的区间比它后面的某个操作的区间小,那么这个操作是无效的, 可以发现有效的操作的区间必定是递减的, 由于只会按照从大到小和从小到大排序, 而每个有效操作的有效区间是它下一个有效区间没有覆盖的部分,所以只需要把原序列 用双指针维护,每次把每个有效操作的有效区间填好就行了。#includeusing namespace std;typedef long long LL;const int N = 1e5 + 10;const int mod = 1e9 + 7;int v[N], q[N];int line[N];int ans[N];int n, qq;int main(){ freopen("data.in","r",stdin); freopen("data.out","w",stdout); int t, x, y, z; scanf("%d", &t); while(t--){ scanf("%d%d%d%d%d%d%d", &v[1], &v[2], &x, &y, &z, &n, &qq); for(int i = 3; i <= n; ++i) v[i] = (v[i - 1] * 1ll * x + y * 1ll * v[i - 2] + z) % mod; q[1] = v[1] % n + 1, q[2] = v[2] % n + 1; for(int i = 3; i <= qq; ++i) q[i] = (y * 1ll * q[i - 1] + x * 1ll * q[i - 2] + z) % n + 1; int en = 0, l = 1, r; for(int i = qq; i ; --i){ if(q[i] > line[en]) line[++en] = q[i]; } if(line[en] >= 2 && v[1] > v[2]) swap(v[2], v[1]); for(int i = line[en] + 1; i <= n; ++i) ans[i] = v[i]; r = line[en]; for(int i = en; i; --i){ for(int j = line[i]; j > line[i - 1]; --j){ if(line[i] & 1) ans[j] = v[l], l++; else ans[j] = v[r], r--; } } LL aans = 0; for(int i = 1; i <= n; ++i){ aans += ans[i] * 1ll * i % mod; if(aans >= mod) aans -= mod; } printf("%I64d\n", aans); } return 0;}
转载地址:http://qyzof.baihongyu.com/