A
发现答案一定至少包含起点或终点中的一个：假设有一种方案不包含，设方案是 (1 < x < y < n)，因为 (a_x eq a_y)，那么一定会有 (a_x eq a_1,a_x eq a_n,a_y eq a_1,a_y eq a_n) 之中的一个（反证即可），所以枚举一下就好了。
B
看错了。。这种不能小块套在大块上。其实每个瓶子下面都需要有隔板。
那么对于每次询问，一定将最大和次大匹配，第三大和第四大匹配。。。。这样就是 (O(n^2)) 的。
事实上你可以拿权值线段树维护区间乘，单点改，全局和。可以做到 (O(n log n))。
C
先将两个矩阵异或。这种东西都要找不变的量。
发现不变的量是行列 (1) 的个数的奇偶性，所以判断一下是否都是偶数即可。
构造：对于 (x>1,y>1)，如果这个位置是 (1)，就操作 ((1,1,x,y))。发现操作后只有第一行和第一列可能不是全(0)。但是注意到每行每列 (1) 的个数都是偶数，所以可以推出都是 (0)。
D
多次看错题浪费时间。。一开始还以为是严格强于区间不同数字的问题后来才发现对 (s_i) 是全局询问。。
一个显然的事实是可以将询问整体平移到 ([0,r-l]) 上。所以现在相当于处理若干的 ([0,k]) 询问。
可以发现相当于坐标轴上有 (n) 个区间 ([s_i,s_i+k])，问区间并长度。我们将 (s_i) 排序，每次只让 (s) 贡献到 ([s_{i},s_{i+1})) 即可，询问离线后排序，双指针维护出 (s_{i+1}-s_{i} leq k) 的和和数量，就可以快速得到答案。
E
因为二进制的性质，有 (2^a + 2^b leq 2^c(a,b < c))。可以发现只有两种可能的木棍可以组合：
- (a < b = c)
- (a = b = c)
我们从小到大考虑每一个数，因为前面的木棒只能用来向后匹配了，并且第一种情况耗费的现在可能有用的木棒最少，所以先处理第一种情况再处理第二种情况。
可以考虑 (>a) 其实是一个限制，所以我们每次肯定贪心取 (<b) 的尽量大的数，这样也可以构造方案了。
看着标签有 FFT 标签，有大佬教我一下怎么 FFT 吗（
F
就差一步想到，我自闭了。
先考虑单次询问怎么做：我们设 (f_{i,0/1}) 表示 (i) 子树合法的方案数，其中 (0/1) 表示父亲边是否割掉。
转移的时候我们先假设全部选择 (f_{x,0})，那么从 (0) 切换到 (1) 的贡献就是 (-f_{x,0}+w_e+f_{x,1})。限制形如至少选 (x) 个，如果是负的我们肯定要选，然后才尽量选择最小的。
接下来有一步我没注意到：如果 (deg_i leq x)，那么 (i) 的所有边可以任意选或不选
于是我们从小到大计算 (x) 的答案，对每个点维护 multiset 表示切掉一条边的所有代价，每次将所有 (deg_i = x) 的点删除（删除形如将这个点所有相邻的点的 multiset 都加入一个边权），然后对森林每个连通块 dp 即可。分析一下我们总遍历的点数：每个点只会在 $ < deg_i$ 的地方被遍历，所以总点数是 (O(sum deg_i) = O(n)) 的。但是这里在每个点求前 (k) 大的和的时候不能每次扫一遍否则会变成 (O(sum deg_i^2))，所以我们维护两个 multiset 分别存前 (k) 小和剩余的元素，每次要询问的时候就暴力调整，通过均摊分析可以证明对于每个点 (i) 形如前 (k) 大的询问单调从 (deg_i) 降到 (0)，每次降低都会贡献 (O( log n)) 的复杂度，所以总复杂度 (O(n log n))。
这种题还是要考虑复杂度是否能和 (sum deg_i) 这种东西扯上关系吧。。
G
神仙构造题。
首先答案的一个下界显然是 (lceil frac{sum hp_i}{n} ceil)，也就是每个士兵都不浪费（除了在打最后一个怪的时候），那么我们提出如下策略：
从前往后考虑所有怪，每次如果这个怪血量 (geq n) 就让所有士兵去打怪，否则设剩余的血量为 (x)，分出若干组士兵，总人数为 (x) 去打这个怪，剩下的士兵同时去考虑下一个怪。
考虑这个过程：如果我们设前缀和为 (s_i)，那么相当于限制了你的划分方案能表示出 (s_i mod n)，一种构造方法是排序后设 (d_i = s_{i}-s_{i-1})，然后发现前缀和就可以表示出所有的数字了。
构造就顺着往下打就可以，因为这种方案是前缀和表示出怪，所以一定是顺着打的。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e6 + 5;
int n,m;
int a[MAXN];
int b[MAXN];
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,m) scanf("%d",a+i);
int sm = 0;std::vector<int> v1;v1.pb(0);v1.pb(n);
FOR(i,1,m-1){
sm += a[i];
v1.pb(sm%n);
}
sm += a[m];
std::sort(all(v1));std::vector<int> sz;
FOR(i,1,(int)v1.size()-1) sz.pb(v1[i]-v1[i-1]);
printf("%d
",(sm+n-1)/n);
for(auto x:sz) printf("%d ",x);puts("");
int p = 0;
FOR(i,1,m){
while(a[i] > 0){
a[i] -= sz[p];++p;
printf("%d ",i);
if(p == (int)sz.size()) puts(""),p = 0;
}
}
if(p) FOR(i,p,m-1) printf("1 ");
puts("");
return 0;
}
H
又是神仙 (FWT) +性质题。。
设集合幂级数 (F_i(s) = xs^{a_i}+ys^{b_i}+zs^{c_i})，那么答案就是 (prod_{i=1}^n F_i)，卷积定义为对称差卷积，这里记异或符号为 (oplus)。
做这种题肯定是要 (FWT) 的，但是直接 (FWT) 时间显然不行，对于这种题我们考虑将 (FWT) 后的式子列出来观察是否能优化。
考虑算 (S) 处的答案，那么 ([s^S]FWT(F_i) = xs^{|a_i cap S|}+ys^{|b_i cap S|} + zs^{|c_i cap S|})。
([s^S]FWT(ANS) = prod_{i=1}^n (xs^{|a_i cap S|}+ys^{|b_i cap S|} + zs^{|c_i cap S|}))，直接计算仍然过不了，但是我们发现这个括号内的式子只有 (8) 种可能。
但是这样还是太多了，我们考虑初始将所有 (a_i,b_i,c_i) 都异或上 (a_i)，那么答案就异或上了 (oplus_{i=1}^n a_i)。
现在只有四种可能了：也就是 (x+y+z,x+y-z,x-y+z,x-y-z)，设这四种可能的方案数分别为 (c_1,c_2,c_3,c_4)，如果能求出方案数就可以快速幂计算出 (FWT(ANS)) 的每一项系数，(IFWT) 回去就做完了。
我们考虑解方程：首先显然有 (c_1 + c_2 + c_3 + c_4 = n)。
我们考虑 ([s^S]sum_{i=1}^n FWT(F_i))，注意到这里的 (x,y,z) 是可以随便取的，但是取 (x) 已经没什么用了，于是我们如果取 (x=0,y=1,z=0)，也是有 (p_1 = [s^S]sum_{i=1}^n FWT(F_i) = sum_{i=1}^n (-1)^{|b_i cap S|} = c_1+c_2-c_3-c_4)，想要计算 ([s^S]sum_{i=1}^n FWT(F_i)) 显然不能暴力，注意到 (FWT) 是一个线性运算（本质是左乘转移矩阵），所以可以直接计算 (FWT(sum_{i=1}^n s^{b_i}))。
同样的 ，如果我们取 (x=0,y=0,z=1)，那么就有 (p_2 = c_1-c_2+c_3-c_4)。
现在因为已经取了 ((0,1,0),(0,0,1))，那么取 (y,z) 的线性组合已经没用了，我们要找到一个不一样的等量。
考虑上面两种情况的对称差卷积的和，也就是 (p_3=[s^S]sum_{i=1}^n FWT(s^{b_i oplus c_i}) = sum_{i=1}^n (-1)^{|b_i cap S|} (-1)^{|c_icap S|})，（对称差卷积等价于 (FWT) 点乘）也就有 (p_3 = c_1-c_2-c_3+c_4)。
这样有方程组：
就可以求出 (FWT(ANS)) 所有的点值，就可以计算答案了。时间复杂度 (O(k2^k +2^klog n))。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
int N;
const int MAXN = 2e5 + 5;
const int ha = 998244353;
const int inv2 = 499122177;
const int inv4 = 748683265;
inline int qpow(LL a,int n=ha-2){
a = (a%ha+ha)%ha;
int res = 1;
while(n){
if(n & 1) res = 1ll*res*a%ha;
a = 1ll*a*a%ha;
n >>= 1;
}
return res;
}
inline void FWT(int f[]){
for(int mid = 1;mid < N;mid <<= 1){
for(int i = 0;i < N;i += (mid<<1)){
FOR(j,0,mid-1){
int x = f[i+j],y = f[i+mid+j];
f[i+j] = (x+y)%ha;f[i+mid+j] = (x+ha-y)%ha;
}
}
}
}
inline void iFWT(int f[]){
for(int mid = N>>1;mid;mid >>= 1){
for(int i = 0;i < N;i += (mid<<1)){
FOR(j,0,mid-1){
int x= f[i+j],y = f[i+mid+j];
f[i+j] = 1ll*(x+y)*inv2%ha;f[i+mid+j] = 1ll*(x+ha-y)*inv2%ha;
}
}
}
}
int n,k;
int a[MAXN],b[MAXN],c[MAXN];
int sm = 0;
int f1[MAXN],f2[MAXN],f3[MAXN],ans[MAXN];
int main(){
scanf("%d%d",&n,&k);N = 1<<k;
int x,y,z;scanf("%d%d%d",&x,&y,&z);
x %= ha;y %= ha;z %= ha;
FOR(i,1,n){
scanf("%d%d%d",a+i,b+i,c+i);
sm ^= a[i];b[i] ^= a[i];c[i] ^= a[i];a[i] = 0;
++f1[b[i]];++f2[c[i]];++f3[b[i]^c[i]];
}
FWT(f1);FWT(f2);FWT(f3);
FOR(i,0,N-1){
LL p1 = f1[i],p2 = f2[i],p3 = f3[i];
LL c1 = 1ll*(n+p1+p2+p3)%ha*inv4%ha;
LL t = 2ll*c1%ha;t = ha-t;
LL c2 = 1ll*(n+p1+t)%ha*inv2%ha;
LL c3 = 1ll*(n+p2+t)%ha*inv2%ha;
LL c4 = 1ll*(n+p3+t)%ha*inv2%ha;
ans[i] = 1ll*qpow(x+y+z,c1)*qpow(x+y-z,c2)%ha*qpow(x-y+z,c3)%ha*qpow(x-y-z,c4)%ha;
}
iFWT(ans);
FOR(i,0,N-1) printf("%d ",ans[i^sm]);
return 0;
}