Legend
Link ( extrm{to Codeforces})。
自我感觉是出的还行的一道题目呀。
Editorial
首先要特判掉只有一个队伍有机器人的情况。
考虑当游戏结束时，总存在至少一个队伍的所有机器人都没有手牌。设此队伍为 (A)，另一队伍为 (B)。当两个队伍的手牌数量总和相同时，我们令 (1) 号机器人的队伍为 (A)。那么，我们已经知道了 (A) 队伍的所有机器人的出牌数量，那么我们只需要计算 (B) 队伍的出牌数量。
我们观察一下这个游戏的进程。显然，(A)，(B) 队伍的机器人是轮流弃牌的。要么是 (ABABABcdots B)，要么是 (BABABAcdots B)。如果我们把后面这种情况暴力消去第一个 (B)，则只有 (ABABABcdots B) 一种情况了。
现在我们只知道有一个这样的出牌序列，但完全不知道哪个字符代表的是哪个机器人。不过我们并不需要知道，因为我们要求的是 (B) 队伍的每个机器人出了多少牌。你可以把序列中的一个 (AB) 子串认为是一个这样的操作：在当前游戏中，某个 (A) 队伍的机器人，导致它右方第一个 (B) 队伍机器人出 (1) 张牌。注意“在当前游戏中”是一个非常重要的限制条件。
但当你手玩几组数据后，你会发现这个“在当前游戏中”一点用都没有，因为无论你以什么顺序执行这些 (AB) 子串的操作，最终得到的 (B) 出牌数量都是一样的。
所以你现在只需要维护一个变量 (cnt)，表示当前已经找到了多少个 (AB) 子串的 (A)，但 (B) 还没有确定人选。然后扫两遍数组（因为是个环）：
- 如果 (i) 是 (A) 队的，我们会找到 (a_i) 个 (A)。将 (cnt) 加上 (a_i)，(a_i) 重置为 (0)。
- 如果 (i) 是 (B) 队的，我们可以找到 (a_i) 个 (B) 与之前的 (A) 来配对。设 (b=min(a_i,cnt))，将 (a_i)，(cnt) 都减去 (b) 即可。
总复杂度就是 (O(n+m)) 的。
Code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 5e6 + 23;
const LL MOD = 1e9 + 7;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int a[MX] ,team[MX] ,org[MX];
int n ,m;
LL s[2];
int seed ,base;
int rnd(){
int ret = seed;
seed = (1LL * seed * base + 233) % MOD;
return ret;
}
int main(){
n = read() ,m = read();
int lastp = 0;
for(int i = 1 ,p ,k ,b ,w ; i <= m ; ++i){
p = read() ,k = read() ,b = read() ,w = read();
seed = b ,base = w;
for(int j = lastp ; j < p ; ++j){
team[j] = rnd() % 2;
s[team[j]] += (org[j] = a[j] = rnd() % k + 1);
}
lastp = p;
}
int st = 0;
if(s[team[0]] > s[!team[0]]){
s[team[0]]-- ,a[0]--;
while(team[0] == team[st] && st < n) ++st;
}
int cur = st;
LL sum = 0;
if(st != n) while(s[team[st]]){
if(team[cur] == team[st]){
sum += a[cur];
a[cur] = 0;
}
else{
LL d = std::min(1LL * a[cur] ,sum);
s[team[st]] -= d;
sum -= d;
a[cur] -= d;
}
cur = (cur + 1 == n ? 0 : cur + 1);
}
LL ans = 1;
for(int i = 0 ; i < n ; ++i){
LL qwq = (((org[i] - a[i]) ^ (1LL * (i + 1) * (i + 1))) + 1) % MOD;
ans = ans * qwq % MOD;
}
printf("%lld
" ,ans);
return 0;
}