「Codeforces 1034E」Little C Loves 3 III
题意
给你两个 \(2^n\) 的数组 \(a_0,..,a_{2^n-1}\) 和 \(b_0,..,b_{2^n-1}\)
在模 \(4\) 意义下求子集卷积
\(n\le 21\)
给你两个 \(2^n\) 的数组 \(a_0,..,a_{2^n-1}\) 和 \(b_0,..,b_{2^n-1}\)
在模 \(4\) 意义下求子集卷积
\(n\le 21\)
有 \(n\) 座城市，第 \(i\) 座城市的人口是 \(w_i\)，有一些无向边。
现在城市被划分为了若干个州，每个州至少包含一个城市，每个城市恰好在一个州内。
设 \(V_i\) 是第 \(i\) 个州的城市集合。
定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 \(0\)），则称这个州是不合法的。
定义第 \(i\) 个州的满意度为：第 \(i\) 个州的人口在前 \(i\) 个州的人口中所占比例的 \(p\) 次幂，即：
\[\left(\frac{\sum_{x\in V_i}w_x}{\sum_{j=1}^i\sum_{x\in V_j}w_x}\right)^p\]
定义一个划分的满意度为所有州的满意度的乘积。
求所有合法的划分方案的满意度之和。
答案对 \(998244353\) 取模。
\(n\le 21,0\le p\le 2\)
时限 \(10s\)
给你两个数组 \(A[0\dotsc 2^m-1]\) 和 \(B[0 \dotsc 2^m-1]\)
你需要计算
\[C[k]=\sum_{i~{\rm and}~j=k}A[i~{\rm xor}~j]\times B[i~{\rm or}~j]\]
输出 \(\sum_{i=0}^{2^m-1}C[i]\times 1526^i \bmod 998244353\)
\(m\le 19\)