P9252 题解

songhongyi · 2024-01-23 11:19:20 · 题解

这个性质让我回想起了某个 CF 的题了。

把红色离子当作 1，绿色离子当作 2，则每次合并后模 3 不变。

因而如此转化后和模 3 为 1 或 2 是一个必要条件。但显然不是充分的。

但是经过手模后，发现貌似除了 1212121 和 2121212 这两种外，都可以构造出解来。

稍加思索，发现貌似确实是这样的。我们只需要证明肯定可以避开这种情况即可。

举例而言，生成 21212 的前驱状态应该是 211112，而我们可以选择 22112 避开这种情况。

注意到与具体的摆放位置无关，因此计数只需要考虑直接算，形如 \binom n 1 + \binom n 4 + \binom n 7 \cdots 之类的。

算这个东西可以考虑 带入单位根 f_{i,0}=f_{i-1,1}+f_{i-1,2} 直接递推预处理。

谨防 n=1 corner case。

//
// Problem: P9252 [PA 2022] Wielki Zderzacz Termionów
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9252
// Memory Limit: 512 MB
// Time Limit: 2000 ms

#include <iostream>
#include <string>
using namespace std;
const int pmod = 1e9 + 7;
int f[ 1000010 ][ 3 ];
int cnt[ 3 ][ 2 ];
int n;
int solve()
{
    if ( n == 1 )
    {
        if ( cnt[ 0 ][ 1 ] )
        {
            return 2;
        }
        else
        {
            return 1;
        }
    }
    int t = abs( cnt[ 1 ][ 0 ] + cnt[ 1 ][ 1 ] - cnt[ 2 ][ 0 ] - cnt[ 2 ][ 1 ] ) % 3,
        s = cnt[ 0 ][ 0 ] + cnt[ 0 ][ 1 ];
    long long int ans = 0;
    if ( t != 0 )
    {
        ( ans += f[ s ][ 0 ] ) %= pmod;
    }
    if ( t != 1 )
    {
        ( ans += f[ s ][ 1 ] ) %= pmod;
    }
    if ( t != 2 )
    {
        ( ans += f[ s ][ 2 ] ) %= pmod;
    }
    if ( n & 1 )
    {
        if ( cnt[ 1 ][ 0 ] == 0 and cnt[ 2 ][ 1 ] == 0 )
        {
            ans--;
        }

        if ( cnt[ 1 ][ 1 ] == 0 and cnt[ 2 ][ 0 ] == 0 )
        {
            ans--;
        }
    }
    return ( ans + pmod ) % pmod;
}
int id( char c )
{
    if ( c == 'C' )
    {
        return 1;
    }
    if ( c == 'Z' )
    {
        return 2;
    }
    if ( c == 'N' )
    {
        return 0;
    }
}
int main()
{
    cin.tie( 0 );
    int m;
    cin >> n >> m;
    string str;
    cin >> str;
    str = " " + str;
    for ( int i = 1; i <= n; i++ )
    {
        cnt[ id( str[ i ] ) ][ i & 1 ]++;
    }
    f[ 0 ][ 0 ] = 1;
    for ( int i = 1; i <= n; i++ )
    {
        f[ i ][ 0 ] = ( f[ i - 1 ][ 1 ] + f[ i - 1 ][ 2 ] ) % pmod;
        f[ i ][ 1 ] = ( f[ i - 1 ][ 0 ] + f[ i - 1 ][ 2 ] ) % pmod;
        f[ i ][ 2 ] = ( f[ i - 1 ][ 1 ] + f[ i - 1 ][ 0 ] ) % pmod;
    }
    cout << solve() << '\n';
    while ( m-- )
    {
        int pos;
        char c;
        cin >> pos >> c;
        cnt[ id( str[ pos ] ) ][ pos & 1 ]--;
        str[ pos ] = c;
        cnt[ id( str[ pos ] ) ][ pos & 1 ]++;
        cout << solve() << '\n';
    }
}