题目
点这里看题目。
分析
可以发现比赛结束必然对应着其中一组的牌打完了。由于打牌是一组一组交错着的,所以必然是牌少的那一组先打完,如果牌相同就是 (t_1) 那一组先打完。
为了方便,我们就记先打完的那一组为 (A) ,后打完的为 (B) 。
接着,根据每次打出牌的机器人的组,我们可以得到两种字符串 ABAB...AB
或者 BABA...BAB
。在第二种情况下,我们可以暴力模拟第一个机器人打牌的过程,所以也可以之间换做 ABAB...AB
。
也就是说, (B) 打出的牌和 (A) 的出的牌数量相同,我们可以将打牌看作是 (A) 中一个机器人打出一张牌,就会导致当前局面下 (A) 之后第一个 (B) 中一个机器人打出一张牌。
注意到我们只考虑最终每个机器人打了多少牌,因此到底是哪个 (A) 让哪个 (B) 打牌,我们不关心。这意味着我们可以直接记录 (B) 还剩多少张牌没打,然后遇到 (A) 就增加这个值,遇到 (B) 就打牌。由于问题在环上,因此我们需要把环扫两遍。
模拟即可得到 (O(n+m)) 的优秀算法。
小结:
- 宏观分析得出了最终打完牌的组。
- 关于打牌的转化,以及忽略顺序的问题简化。
代码
#include <cstdio>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int mod = 1e9 + 7;
const int MAXN = 5e6 + 5, MAXM = 2e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
LL ans[MAXN];
LL A[MAXN], T[MAXN];
int N, M;
namespace Generate
{
int seed = 0, base = 0;
int Rnd()
{
int ret = seed;
seed = ( 1ll * seed * base + 233 ) % mod;
return ret;
}
}
void Input()
{
read( N ), read( M );
for( int i = 1, lst = 0 ; i <= M ; i ++ )
{
int p, k, b, w;
read( p ), read( k ), read( b ), read( w );
Generate :: seed = b, Generate :: base = w;
rep( j, lst + 1, p )
T[j] = ( Generate :: Rnd() & 1 ),
A[j] = ( Generate :: Rnd() % k ) + 1;
lst = p;
}
}
int main()
{
Input();
LL su[2] = {};
rep( i, 1, N ) su[T[i]] += A[i];
int los = su[0] == su[1] ? T[1] : su[0] > su[1];
int beg = 1;
if( los ^ T[1] )
{
ans[1] ++, A[1] --;
for( ; beg <= N && T[beg] ^ los ; beg ++ );
}
LL cnt = 0;
for( int i = 1, stp = N << 1 ; stp ; i = i % N + 1, stp -- )
{
if( T[i] == los ) cnt += A[i], ans[i] += A[i], A[i] = 0;
else
{
LL delt = MIN( cnt, A[i] );
A[i] -= delt, ans[i] += delt, cnt -= delt;
}
}
int prt = 1;
rep( i, 1, N )
prt = 1ll * prt * ( ( ans[i] ^ ( 1ll * i * i ) ) % mod + 1 ) % mod;
write( prt ), putchar( '
' );
return 0;
}