首页 > 其他分享 >「ARC134E」Modulo Nim

「ARC134E」Modulo Nim

时间:2022-11-21 16:45:37浏览次数:71  
标签:return Nim int ARC134E vec && inline Modulo const

题目

点这里看题目。


有一个长度为 \(n\) 的非负整数序列 \(\{a_i\}_{i=1}^n\),Amily 和 Bonnie 会在上面玩一个游戏。

双方会轮流执行如下操作,且 Amily 先手:

设 \(M=\max_{1\le i\le n} a_i\)。

如果 \(M=0\),则当前操作的一方获胜

否则,操作方需要选定一个 \([1,M]\) 内的整数 \(x\),并对于 \(1\le i\le n\),令 \(a_i\gets a_i\bmod x\)。

但是,将进行游戏的 \(a\) 序列尚未确定。具体来说,有另一个正整数参数序列 \(\{R_i\}_{i=1}^n\) 用于生成 \(\{a\}\):对于 \(1\le i\le n\),\(a_i\) 会是 \([1,R_i]\) 中的一个整数。

Amily 想要知道,在所有的 \(\prod_{i=1}^n R_i\) 种情况中,有多少种情况可以使她有必胜策略?你只需要告诉她答案对 \(998244353\) 取模后的结果。

所有数据满足 \(1\le n\le 200,1\le R_i\le 200\)。

分析

有了 NOI 2022 的糟糕经历,看到这种题就难受起来了。

按部就班。首先考虑给定一个序列时,如何判定 Amily 是否有必胜策略。在此之前,我们注意到重复的数变化一致,所以我们仅仅关心序列的值的集合,记其为 \(S\)。顺便记 \(M=\max S\)。

常规想法:思考一些“傻瓜策略”,看能不能奏效。具体过程见下:

  • 如果 \(M=0\),那么是必胜的,甚至不用策略

  • 如果 \(x=1\),此时必须有 \(M\ge 1\)。这是“必败策略”。

  • 如果 \(x=2\),此时必须有 \(M\ge 2\)。

    注意到,一旦存在奇数,则 Amily 操作后 Bonnie 拿到的就是 \(S=\{1\}\) 或 \(S=\{0,1\}\),总之就是必败。

    所以,如果存在奇数则必胜。相应地,之后讨论时我们假设 \(S\) 中的数全为 \(2\) 的倍数

  • 如果 \(x=4\),此时必须有 \(M\ge 4\)。

    类似地,此时如果存在 \(4k+2\) 的数,则 Amily 操作后 Bonnie 拿到的非 \(S=\{2\}\) 即 \(S=\{0,2\}\),仍然必败。

    所以,如果存在非 \(4\) 倍数则必胜。

  • 如果 \(x=3\),此时必须有 \(M\ge 3\)。

    无非是讨论余数存在情况。此时我们发现,如果 \(3k+1\) 和 \(3k+2\) 恰好有一个存在则可以获胜。

当然可以接着讨论,但是就太麻烦了。而且我们也意识到讨论所有 \(x\) 并不现实。为了结束无休无止的讨论,我们的办法就是把剩下的两个情况全部讨论出来

  • 如果 \(3k+1\) 和 \(3k+2\) 同时存在,且 \(S\) 中的数全是 \(4\) 的倍数。

    这一类情况中,\(M\) 最小的 \(S\) 为 \(\{4,8\}\),经过暴力验证发现它不存在 Amily 的必胜策略。

    更大的情况可以打表找规律,结果就是这种情况下只有 \(\{4,8\}\) 没有必胜策略,其它都有

    Note.

    我也尝试过打表,但是一头雾水。

    问题在于打表没有针对性。如果可以结合讨论的结果,那么一些结论就很好发现了。

    对于这一点有一个很巧妙的构造——除了 \(\{4,8\}\) 之外,其它情况下 \(M>12\),而上面的讨论仅和元素模 \(12\) 的余数相关,所以操作一次 \(x=12\) 不会改变讨论结果。因此,\(M>12\) 时,如果上面讨论出了必胜策略则直接操作,否则可以先操作 \(x=12\),让 Bonnie 拿到必败态,这样 Amily 还是有必胜策略。

  • 否则,\(S\) 中的数全是 \(12\) 的倍数。

    我们注意到,此时我们可以 \(O(M)\) 地判断一个 \(S\) 是否有必胜策略:只需要枚举第一次操作的 \(x\),之后的就可以套用讨论的结果。

    事实上,“全是 \(2\) 的倍数”、“全是 \(4\) 的倍数”也可以这样操作。但这种情况和它们有本质区别——可能的 \(12\) 的倍数只有 \(16\) 个,也就是 \(S\) 只有 \(2^{16}-1\) 种情况。我们完全可以暴力检查这 \(2^{16}-1\) 种情况是否有必胜策略!

    Remark.

    如果你对数据范围起过疑心,那么也应当可以想到暴力检查的策略。

上面的讨论还指出,不存在必胜策略的情况非常少,所以我们减去这样的局面的数量即可。各个情况之间没有重叠,因此操作起来并不困难,不过需要额外注意一些 \(M\) 较小的必败局面。

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = 205, MAXS = ( 1 << 12 ) + 5, MAXL = ( 1 << 16 ) + 5;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

int lrg[MAXL];

int f[2][MAXL];
int g[2][4];

int A[MAXN];

int N, mx = 0;

inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }

inline bool ChkMEq2( const std :: vector<int> &vec ) {
    for( const int &x : vec )
        if( x % 2 == 1 ) return true;
    return false;
}

inline bool ChkMEq3( const std :: vector<int> &vec ) {
    bool rem[3] = {};
    for( const int &x : vec )
        rem[x % 3] = true;
    if( ( rem[1] && ! rem[2] ) || ( rem[2] && ! rem[1] ) )
        return true;
    if( rem[1] && rem[2] ) 
        return ! ( vec.size() == 2u && vec[0] == 4 && vec[1] == 8 );
    return false;
}

inline bool ChkMEq4( const std :: vector<int> &vec ) {
    for( const int &x : vec )
        if( x % 4 == 2 ) return true;
    return false;
}

inline std :: vector<int> Modular( std :: vector<int> vec, const int &m ) {
    std :: vector<int> ret;
    for( int &x : vec ) x %= m;
    std :: sort( vec.begin(), vec.end() );
    vec.erase( vec.end() = std :: unique( vec.begin(), vec.end() ), vec.end() );
    for( const int &x : vec ) 
        if( x > 0 ) ret.push_back( x );
    return ret;
}

bool DFS( const std :: vector<int> &vec ) {
    if( vec.empty() ) return true;
    int up = 0;
    for( const int &x : vec )
        up = std :: max( up, x );
    if( vec.size() == 1u ) return vec[0] > 2;
    if( up >= 2 && ChkMEq2( vec ) ) return true;
    if( up >= 3 && ChkMEq3( vec ) ) return true;
    if( up >= 4 && ChkMEq4( vec ) ) return true;
    if( up >= 3 && vec.size() == 2u && vec[0] == 4 && vec[1] == 8 ) return false;
    int S = 0;
    for( const int &x : vec )
        S |= 1 << ( x / 12 - 1 );
    if( ~ lrg[S] ) return lrg[S];
    lrg[S] = 0;
    for( int m = 5 ; m <= up ; m ++ )
        if( ! DFS( Modular( vec, m ) ) ) {
            lrg[S] = 1; break;
        }
    return lrg[S];
}

inline bool Chk( const int &S ) {
    std :: vector<int> vec;
    for( int i = 0 ; i < mx ; i ++ )
        if( S >> i & 1 ) vec.push_back( ( i + 1 ) * 12 );
    return DFS( vec );
}

inline bool Only2() {
    rep( i, 1, N )
        if( A[i] < 2 )
            return false;
    return true;
}

inline bool Only1() {
    rep( i, 1, N )
        if( A[i] < 1 )
            return false;
    return true;
}

int main() {
    Read( N ); int ans = 1;
    rep( i, 1, N ) {
        Read( A[i] ); 
        MulEq( ans, A[i] );
        mx = std :: max( mx, A[i] );
    }
    int pre = 1, nxt = 0;
    mx /= 12, f[nxt][0] = 1;
    rep( i, 1, N ) {
        pre ^= 1, nxt ^= 1;
        for( int S = 0 ; S < ( 1 << mx ) ; S ++ ) {
            if( ! f[pre][S] ) continue;
            for( int j = 0 ; j < mx ; j ++ )
                if( 12 * ( j + 1 ) <= A[i] )
                    AddEq( f[nxt][S | ( 1 << j )], f[pre][S] );
            f[pre][S] = 0;
        }
    }
    memset( lrg, -1, sizeof lrg );
    for( int S = 0 ; S < ( 1 << mx ) ; S ++ )
        if( ! Chk( S ) ) SubEq( ans, f[nxt][S] );
    pre = 1, nxt = 0, g[nxt][0] = 1;
    rep( i, 1, N ) {
        pre ^= 1, nxt ^= 1;
        for( int S = 0 ; S < 4 ; S ++ ) {
            if( ! g[pre][S] ) continue;
            if( A[i] >= 4 ) AddEq( g[nxt][S | 1], g[pre][S] );
            if( A[i] >= 8 ) AddEq( g[nxt][S | 2], g[pre][S] );
            g[pre][S] = 0;
        }
    }
    SubEq( ans, g[nxt][3] );
    SubEq( ans, Only1() );
    SubEq( ans, Only2() );
    Write( ans ), putchar( '\n' );
    return 0;
}

标签:return,Nim,int,ARC134E,vec,&&,inline,Modulo,const
From: https://www.cnblogs.com/crashed/p/16911864.html

相关文章