题解说明

问题背景：
给定一个长度为 $n$ 的序列，每个位置的元素类型为 'N'、'C' 或 'Z'，分别映射为 $0,1,2$。
要求计算满足某种模 $3$ 条件的方案数，并支持 $q$ 次修改操作（修改某个位置的类型），每次修改后都要输出新的答案。
结果对 $10^9+7$ 取模。

核心思路：

$1.$ 类型映射与统计：

• 将输入字符 'N'、'C'、'Z' 分别映射为 $0,1,2$。
• 维护：
  • $cnt[0][t]$：偶数下标位置中类型 $t$ 的数量。
  • $cnt[1][t]$：奇数下标位置中类型 $t$ 的数量。
  • $tot[t]$：全局类型 $t$ 的数量。

$2.$ 动态规划预处理：

• 定义 $f[i][j]$：表示前 $i$ 个 'N' 类型中，选择子集后模 $3$ 余数为 $j$ 的方案数。
• 转移：
  • $f[i][0] = f[i-1][0] + f[i-1][2]$
  • $f[i][1] = f[i-1][1] + f[i-1][0]$
  • $f[i][2] = f[i-1][2] + f[i-1][1]$
• 这样 $f[tot[0]][j]$ 就表示所有 'N' 类型的子集在模 $3$ 下的分布。
• 同时预处理 $pw[i] = 2^i \bmod Mod$，表示 'N' 类型的总选择数。

$3.$ 答案计算逻辑：

• 目标是总方案数减去“不合法”的方案数。
• 总方案数为 $2^{tot[0]}$。
• 不合法方案数：
  • 根据 $C$、$Z$、$N$ 的数量，计算需要排除的模 $3$ 值 $x = (-tot[1] - 2\cdot tot[2] - tot[0]) \bmod 3$。
  • 不合法的基础数量为 $f[tot[0]][x]$。
• 特殊情况：当 $n$ 为奇数且 $n \ne 1$ 时，还需额外排除两类情况：
  • 奇位无 $C$ 且偶位无 $Z$。
  • 偶位无 $C$ 且奇位无 $Z$。
• 最终答案：
  $\text{ans} = 2^{tot[0]} - \text{不合法方案数}$ （取模）。

$4.$ 修改操作：

• 每次修改位置 $x$ 的类型：
  • 从 $cnt$ 和 $tot$ 中移除旧类型。
  • 更新为新类型并加入统计。
• 然后重新调用 get_ans() 输出答案。
• 因为 $f$ 和 $pw$ 已经预处理好，修改时只需 $O(1)$ 更新统计并 $O(1)$ 输出答案。

复杂度分析：

• 预处理 $O(n)$。
• 每次修改 $O(1)$。
• 总体复杂度 $O(n+q)$，适合 $n,q \leq 2 \times 10^5$。

#include <bits/stdc++.h>
#define Mod 1000000007  // 结果取模的模数（1e9+7）
using namespace std;

/**
 * 快速读取整数函数
 * 功能：高效读取正整数，跳过非数字字符，适用于大量输入场景
 * 返回值：读取到的整数
 */
int Qread() {
    int x = 0;
    char ch = getchar();

    // 跳过所有非数字字符
    while (ch < '0' || ch > '9')
        ch = getchar();

    // 读取数字并转换为整数（ch^48 等价于 ch-'0'）
    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();

    return x;
}

/**
 * 获取类型函数
 * 功能：读取字符并映射为对应类型（N→0，C→1，Z→2）
 * 返回值：类型对应的整数（0/1/2）
 */
int get_typ() {
    char ch = getchar();

    // 跳过无关字符，只保留'N'/'C'/'Z'
    while (ch != 'N' && ch != 'C' && ch != 'Z')
        ch = getchar();

    // 类型映射
    if (ch == 'N') return 0;
    else if (ch == 'C') return 1;
    else return 2;
}

// 全局变量定义
int n, q, x;               // n：初始元素总数；q：修改查询次数；x：当前修改的位置
int a[200010];             // 存储每个位置的类型（0/1/2对应N/C/Z）
int cnt[2][3];             // 按位置奇偶性统计类型数量：cnt[0][t]为偶位类型t的数量，cnt[1][t]为奇位类型t的数量
int tot[3];                // 三种类型的总数量（不区分奇偶位）
int f[200010][3];          // DP数组：f[i][j]表示前i个N类型中，满足特定条件且模3为j的数量
int pw[200010];            // 存储2的幂次：pw[i] = 2^i % Mod（N类型的总选择情况数）

/**
 * 模运算调整函数
 * 功能：确保数值在[0, Mod)范围内，避免负数或溢出
 * 参数：a - 待调整的数值
 * 返回值：调整后的数值
 */
int chk(int a) {
    return a >= Mod ? a - Mod : a;
}

/**
 * 计算并输出答案
 * 功能：根据当前类型统计结果，计算满足条件的情况数
 * 逻辑：总情况数（2^tot[0]）减去不满足条件的情况数
 */
void get_ans() {
    // 计算目标模3值x：根据C、Z、N的总数量推导需排除的状态
    int x = (-tot[1] - 2 * tot[2] - tot[0]) % 3;
    if (x < 0) x += 3;  // 确保x为非负（0/1/2）

    // 不满足条件的基础数量：前tot[0]个N类型中模3为x的情况数
    int ans = f[tot[0]][x];

    // 特殊情况：n为奇数且n≠1时，需额外判断奇偶位的类型限制
    if ((n & 1) && n != 1) {
        // 条件1：奇位无C（1）且偶位无Z（2）→ 新增1种无效情况
        if (cnt[1][1] == 0 && cnt[0][2] == 0)
            ans++;
        // 条件2：偶位无C（1）且奇位无Z（2）→ 新增1种无效情况
        if (cnt[0][1] == 0 && cnt[1][2] == 0)
            ans++;
        ans = chk(ans);  // 调整模值
    }

    // 最终答案 = 总情况数 - 无效情况数（加Mod避免负数）
    ans = chk(pw[tot[0]] + Mod - ans);
    printf("%d\n", ans);
}

int main() {
    // 读取初始参数
    n = Qread(), q = Qread();

    // 初始化类型统计：记录每个位置的类型，更新奇偶位计数和总计数
    for (int i = 1; i <= n; i++) {
        a[i] = get_typ();                // 读取第i个位置的类型
        cnt[i & 1][a[i]]++;              // i&1判断奇偶位（1为奇，0为偶），对应计数+1
        tot[a[i]]++;                     // 总计数+1
    }

    // 预处理DP数组和幂次数组
    f[0][0] = 1;  // 初始状态：0个N时，模3为0的情况数为1（空集）
    pw[0] = 1;    // 2^0 = 1
    for (int i = 1; i <= n; i++) {
        // DP状态转移：基于前i-1个N的状态推导
        f[i][0] = chk(f[i - 1][0] + f[i - 1][2]);  // 模3=0的状态来自前i-1个的0和2
        f[i][1] = chk(f[i - 1][1] + f[i - 1][0]);  // 模3=1的状态来自前i-1个的1和0
        f[i][2] = chk(f[i - 1][2] + f[i - 1][1]);  // 模3=2的状态来自前i-1个的2和1
        pw[i] = chk(pw[i - 1] << 1);               // 2^i = (2^(i-1) * 2) % Mod（左移等价乘2）
    }

    // 计算初始答案
    get_ans();

    // 处理q次修改查询
    while (q--) {
        x = Qread();  // 读取修改位置x

        // 移除旧类型的计数
        cnt[x & 1][a[x]]--;  // 旧类型在对应奇偶位的计数-1
        tot[a[x]]--;         // 旧类型的总计数-1

        // 更新为新类型
        a[x] = get_typ();

        // 添加新类型的计数
        cnt[x & 1][a[x]]++;  // 新类型在对应奇偶位的计数+1
        tot[a[x]]++;         // 新类型的总计数+1

        // 计算修改后的答案
        get_ans();
    }

    return 0;
}