题解：P9049 [PA 2021] Mopadulo

__biu_biu_biu__ · 2026-07-20 21:26:15 · 题解

将长度为 n 的序列 A 划分成若干段，使得每一段的和模 10^9+7 都是偶数，求划分方案数。答案对 10^9+7 取模。1\le n\le 3\times 10^5。

考虑 dp_i 表示将前 i 个划分成若干满足条件的段的方案数，为了方便，我们记 f(l,r) 表示 \sum\limits_{l\le x\le r}A_x\bmod 10^9+7 的值。

有转移 dp_i=\sum\limits_{1\le j<i\land f(j+1,i)\bmod 2=0}dp_{j}。

这个转移用前缀和优化是 O(n^2) 的，考虑优化。

注意到 f(j+1,i) 的奇偶性满足：

• 如果 f(1,i)>f(1,j) 且 f(1,i) 与 f(1,j) 相同奇偶性，则 f(j+1,i) 是偶数。
• 如果 f(1,i)<f(1,j) 且 f(1,i) 与 f(1,j) 不相同奇偶（因为要加上 10^9+7 变成正数，奇偶会改变）则 f(j+1,i) 是偶数。

因此考虑对 f(1,i) 的奇偶性建两棵线段树，每次查询找相同奇偶性且值小于它的、和不同奇偶性且值大于它的，转移时区间求和单点赋值。时间复杂度 O(n\log V),V=10^9+7。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5, mod = 1e9 + 7;
int n, s[N], dp[N], o[N];
int summ[N], m;
int sum[2][N << 2];
int tot[2];

void upd(int fg, int p, int k, int l, int r, int rt) {
    if (l == r) {
        sum[fg][rt] = (sum[fg][rt] + k) % mod;
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid) upd(fg, p, k, l, mid, rt << 1);
    else upd(fg, p, k, mid + 1, r, rt << 1 | 1);
    sum[fg][rt] = (sum[fg][rt << 1] + sum[fg][rt << 1 | 1]) % mod;
}

int qry(int fg, int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return sum[fg][rt];
    int mid = l + r >> 1, res = 0;
    if (L <= mid) res = (res + qry(fg, L, R, l, mid, rt << 1)) % mod;
    if (R > mid) res = (res + qry(fg, L, R, mid + 1, r, rt << 1 | 1)) % mod;
    return res;
}

int main() {
    cin >> n;
    summ[0] = s[0] = 0; o[0] = 0;
    for (int i = 1, a; i <= n; ++i) {
        cin >> a;
        s[i] = (s[i - 1] + a) % mod;
        o[i] = s[i] & 1;
        summ[i] = s[i];
    }
    sort(summ, summ + n + 1);
    m = unique(summ, summ + n + 1) - summ;
    for (int i = 0; i <= n; ++i)
        s[i] = lower_bound(summ, summ + m, s[i]) - summ + 1;

    dp[0] = 1;
    upd(0, s[0], dp[0], 1, m, 1);
    tot[0] = 1;

    for (int i = 1; i <= n; ++i) {
        int anss1 = qry(o[i], 1, s[i], 1, m, 1);
        int anss2 = (tot[o[i] ^ 1] - qry(o[i] ^ 1, 1, s[i], 1, m, 1) + mod) % mod;
        dp[i] = (anss1 + anss2) % mod;
        upd(o[i], s[i], dp[i], 1, m, 1);
        tot[o[i]] = (tot[o[i]] + dp[i]) % mod;
    }
    cout << dp[n] << '\n';
    return 0;
}

:::