题意：

给定一个n 个元素的数组，每个元素有 颜色 $c_i$ 和价值 $w_i$

选定一个序列，序列中相邻的同颜色的元素会被装订在一起成为一批

特别地，若没有一个元素没有相邻的同颜色元素，那么它会被单独装订

序列的价值为 每一批的总价值的平方的 和

求所有序列的价值和 ，对 $998244353$ 取模

思路：

对于当前新增的元素，考虑它对前面所有序列的影响

即前面所有序列后面跟上它之后的影响

这个价值算出来，再加上之前的所有序列的贡献

就是当前新增元素的价值总和

不妨记 $f_i$ 表示考虑到第 $i$ 个元素 的所有序列价值和，那么有

$f_i =f_{i-1}+w$

现在就是这个 $w$ 比较难算

我们对前面的序列拆分讨论

• 假设选中序列 $S$ , $S$ 的末尾元素颜色不是 $c_i$

  • 那么对于 $S$ , $i$ 的贡献就是 $W_S + w^2_i$

    • 到这一步，我们就能拿到所有 $c_i$ 互不相同的分数了

    • 新增元素的贡献就是前面所有不同序列的个数

    • 不同的序列的个数怎么算呢？

      • 根据组合数 $C^n_m=n! /(n-m)!$

      • 则不重不漏的 $C^n_m = n!/[(n-m)!\times m!]$

      • 由于有模意义下的除法，所以我们需要总结更优秀的公式

    • 杨辉三角？杨辉三角的一个层

      • 假设当前在第 $i$ 层，那么答案就是杨辉三角第 $i+1$ 层的和 - 1

      • 再根据杨辉三角，我们得到一个惊人的结论

      • 第 $i$ 层的和 就是 $2^{i-1}$

    • 所以前 $i-1$ 各元素的序列个数即为 $2^{i-1} -1$

• 所以我们顺带的把当前元素之前的所有序列的个数算出来了

  • 那么 $c_i$ 互不相同的计数即为 当前 元素价值平方 乘上 前面序列个数 再加上 $f_{i-1}$
  • 别忘了，自己成为一个序列，所以应当 是 $2^{i-1}$

• 假设选中 $S$ ， 末尾元素颜色是 $c_i$，这时候 怎么处理呢？

  • 我们此时得把 $S$ 拆开，拆成前面的无关影响和后面的同颜色相邻元素
  • $W_{无关} + W_{c_i}$ , 此时再拼一个 $c_i$ 到末尾
  • 我们把原先的 $W_{c_i}$ 拆开
  • 得到 $(c_{i,1}+c_{i,2}+c_{i,3}+\dots+c_{i,k})^2$
  • 简化并展开，分解得到
  • $a^2_1+a^2_2+a^2_3+\dots+a^2_k +$
  • $2\times(a_1\times a_2+a_1\times a_3+\dots+a_1\times a_k) +$
  • $2\times(a_2\times a_3+a_2\times a_4+\dots+a_2\times a_k) +$
  • $\dots$
  • $2\times a_{k-1}\times a_k$
  • 此时再拼一个 $c_i$ 到末尾 $(a_{k+1})$
  • 就是前面所有这些的贡献再
  • $+ a^2_{k+1} + 2\times(a_1+a_2+a_3+\dots+a_k)\times a_{k+1}$

• 现在问题已经变得不再复杂，我们有推第一种情况的序列个数

• 对于新增贡献的 $a^2_{k+1}$ 这一项 ,因为对每一个序列都生效

• 我们就会发现要乘以序列个数 $2^{i-1}$

• 对于以 颜色 $c_i$ 为结尾的序列 ，要单独拎出来

  $2\times(a_1+a_2+a_3+\dots+a_k)\times a_{k+1}$
  

• 这一项我们该怎么处理呢？

  • 这是对于每一个以 $a_k$ 为结尾的序列

  • 我们发现只要处理括号内元素的总和即可

• 当颜色 $c_i$ 前方没有相同颜色的时候 ， 以它为结尾的序列的个数有 $2^{i-1}$ 个

• 当颜色 $c_i$ 前方只有一个相同颜色的位置为 $j$ 的时候 ，以 $j$ 为结尾的序列个数有 $2^{j-1}$ 个

  • 那么 相应的 ， $j$ 对于 $i$ 就贡献了 $2\times a_j\times 2^{j-1}$ 的倍数 ，即新增这个倍数 $\times a_i$ 的价值

  • 那么对于下一个 相同颜色位置 $k$ 呢？

  • 相当于是以 $j$ 为结尾的序列个数提供的倍数

    • 次数 $2^{j-1}$

  • 再加上以 $i$ 为结尾且相同颜色只有一个的序列个数提供的倍数

    • 次数 $2^{i-1} - 2^{j-1}$

  • 再加上包含 $j,i$ 的序列个数倍数

    • $2\times (a_j+a_i)$

  • 那么它出现了多少次呢？

    • $2^{j-1}$ 次

  • 那么他们总的提供价值为

$4\times a_j\times 2^{j-1}+2\times a_i\times 2^{i-1}$

我们可以把 $2$ 放进幂，简化后相当于

$2^j\times2\times a_j+2^i \times a_i$

• 很容易想到递推
  • 不过怎么计算这个递推的倍数和呢？
• 我们新放一个 $k$ 进去
• 给后方元素的倍数和即为

$2^j\times 4\times a_j+2^i\times 2\times a_i+2^k\times a_k$

我们很容易想到 ，实质上是

对于每个位置，它的贡献每次翻两倍

---

这一段是进入误区

我们现在把点的贡献记为

$[2^{pos},\sum^{now}_{pos} a_{pos}, w_{now}]$

其中，第一项代表节点 幂次 ，第二项代表节点到现在已经累积的同颜色和

第三项代表节点给现在下标颜色提供的倍数和

我们每一次新增一个元素 $v$

实际上是

先计入 $\sum^{now-1}_1 2^t$ 的贡献

在计入前面所有 $w_t$ 的贡献

再给所有的前方相同颜色 第二项增加 $a_v$

再给当前位置增加当前节点贡献

再使得所有前方的 $w_t$ 增加 第一项乘第二项

听起来这样还是有点难维护

就是最后的独立增加第一项乘第二项

思考更优秀的维护方法

---

所以可以记 $wn_{c}$ 为颜色 $c$ 的当前总倍数和

每次遇见一个 颜色 $c$ , 先使页数乘以这个倍数和

然后用它的幂次去算它提供的倍数和

使得总倍数乘二

加入总倍数

---

Code

int n,col[N],a[N];//节点的价值 
ll mc[N],wn[N],f[N]; 
void solved(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>col[i];
    for(int i=1;i<=n;i++)cin>>a[i];
    mc[0]=1;
    for(int i=1;i<=n;i++)mc[i]=mc[i-1]*2%mod;
    for(int i=1;i<=n;i++){
        int c=col[i];//对于前面所有序列的贡献 
        f[i]=(f[i-1]+f[i-1]+(ll)a[i]*a[i]%mod*mc[i-1]%mod)%mod; 
        f[i]=(f[i]+wn[c]*a[i]%mod)%mod;//总倍数和 
        wn[c]=(2*wn[c]+a[i]*mc[i]%mod)%mod;
    }//当前颜色供给后方颜色的总贡献倍数递推 
    cout<<f[n];
}

---

总时间复杂度是 $O(n)$ 的，递推算前缀和不停维护即可

难度是青还算合理，我是因为不懂所有序列个数推了一个小时 属于见过就比较简单，没见过要推个把小时

分批装订：解法与部分分

如果枚举选了哪些材料，可以直接算费用，但共有 $2^n-1$ 种方案．考虑按原顺序加入材料，把已有方案分成“不选当前材料”和“选当前材料”两类．

令 $C$ 为此前的方案数，包含空方案；$A$ 为这些方案的费用总和．设当前材料类别为 $c$、页数为 $w$．

追加材料后，每个方案原来的费用保留，又会增加 $w^2$．如果原方案最后一批也是类别 $c$，设这批已有 $s$ 页，那么从 $s^2$ 变成 $(s+w)^2$，还多了 $2ws$．问题因此落到：能否得到这些最后一批页数的总和？

设 $F_c$ 为所有末尾类别是 $c$ 的方案中，最后一批的页数之和．它不是方案费用，也不记录更早的批次．于是

$$A'=2A+w^2C+2wF_c.$$

其中一个 $A$ 来自不选，另一个来自选了但保留原来的费用．空方案追加当前材料同样成立，它原来的最后一批页数视为零．

再更新 $F_c$．不选时留下旧的 $F_c$；选时，旧末批为 $c$ 的方案继续保留原页数，贡献又一个 $F_c$；所有旧方案都加上当前的 $w$ 页，贡献 $wC$．因此

$$F_c'=2F_c+wC,\qquad C'=2C.$$

其他类别的 $F$ 不变，因为新产生的方案都以类别 $c$ 结束．三条式子的右边必须使用更新前的值．初始 $C=1,A=0,F_c=0$．每个子序列恰好由唯一的选择过程产生，所以既没有遗漏也没有重复．

时间 $O(n)$，空间 $O(n)$．运算全部取模，乘法先转 64 位．

部分分

• 子任务 1： 枚举位置子集，再扫描选出的序列分批，$O(n2^n)$．
• 子任务 2： 类别各不相同，永远不会合批．每份材料出现在 $2^{n-1}$ 个子序列中，答案为 $2^{n-1}\sum w_i^2$，$O(n)$．
• 子任务 3： 只有一类，费用为所有选中页数之和的平方．维护方案数、页数和、页数平方和即可，$O(n)$；这是理解需要保留哪些统计量的入口．
• 子任务 4： 拆平方，单点贡献同子任务 2．同类位置 $i<j$ 同批的条件是：两点都选，中间其他类别全不选，中间同类可选可不选．设中间同类有 $t$ 个，外部位置与这 $t$ 个位置自由选择，所以该对贡献 $2w_iw_j2^{i-1+n-j+t}$．枚举点对并累计中间同类数量，$O(n^2)$ 时间、$O(n)$ 空间．
• 子任务 5： 按最后类别维护方案数、末批页数和、费用和．追加材料时枚举原末尾类别，决定合批还是新开一批，$O(nK)$ 时间、$O(K)$ 空间，$K\le20$．空方案单独处理．
• 子任务 6： 把所有类别转移中的公共项合并为 $C,A$，只修改 $F_c$，得到上述线性做法．

参考程序

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll mod = 998244353;
void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> c(n);
    for (int &x : c) cin >> x;
    vector<ll> f(n + 1);
    ll ans = 0, cnt = 1;
    for (int i = 0; i < n; i++) {
        ll w;
        cin >> w;
        w %= mod;
        ans = (2 * ans + w * w % mod * cnt + 2 * w % mod * f[c[i]]) % mod;
        f[c[i]] = (2 * f[c[i]] + w * cnt) % mod;
        cnt = cnt * 2 % mod;
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
#ifdef SELF_TEST_BATCH
    cin >> t;
#endif
    while (t--) solve();
}