AT_abc321_f 题解

· · 题解

题意

有一个可重集合 S，初始为空。每次往 S 中增添或删除一个元素，求在每次操作后 S 的和为 K 的子集的个数。不同位置元素构成相同集合视为不同子集。

操作次数，不超过 5000，K 和操作中的元素均不超过 5000，保证操作合法。

解法

这十分甚至九分地像一个生成函数的形式，把它写出来，则答案的生成函数为

\prod_{i\in S} (1+x^i)

它的 x^K 项系数就是答案。x^{K+1} 以上的系数显然可以忽略。

赛时妄想用 NTT 直接求能过，浪费 25min，外加一发罚时，警钟长鸣，不要低估 NTT 等的常数。

你发现这个东西多乘上一个元素 a 是容易处理的，直接暴力乘到原多项式中，就是 O(K) 的。

然后考虑删去元素 a 是该怎么处理。

设删去 a 后的多项式为 A，则对于原多项式 B，有：

A+x^aA=B

放到每一项系数中，就有

B_i=A_i+A_{i-a}

其中 A_i,B_i 分别表示 A,B 中 x^i 项的系数。

显然有 A_i=B_i-A_{i-a}，直接从小到大每项处理即可。

时间复杂度 O(QK)，其中 Q 是操作个数。

代码

极度舒适。

#include <iostream>
#include <cstdio>
#include <vector>
#pragma GCC optimize(2)
using namespace std;
const int mod = 998244353;
int a[5005], k, q;//a[i] 是多项式的系数
int main(){
    cin >> q >> k;
    a[0] = 1;
    while(q--){
        char op;
        int x;
        cin >> op >> x;
        if(op == '+')
            for(int i = 5000; i >= x; i--)  
                (a[i] += a[i - x]) %= mod;
        else
            for(int i = x; i <= 5000; i++)
                (a[i] += mod - a[i - x]) %= mod;
        //注意顺序，一正一反
        cout << a[k] << endl;
    }
    return 0;
}