2023thupc总结

A 大富翁
很有意思的题
${\sum }_{x\in A}{\sum }_{y\in B}[x支配y]-{\sum }_{x\in A}{\sum }_{y\in B}[y支配x]-{\sum }_{x\in A}{w}_x$
$={\sum }_{x\in A}{\sum }_y[x支配y]-{\sum }_{x\in A}{\sum }_y[y支配x]-{\sum }_{x\in A}{w}_x$
$={\sum }_{x\in A}si{z}_x-{\sum }_{x\in A}de{p}_x-{\sum }_{x\in A}{w}_x$
这样每个点的贡献就确定了
排序后取奇数位

C 快速最小公倍数变换
考虑把贡献改写成一个只跟$r_i$相关，只跟$r_j$相关，只跟$r_i+r_j$相关的三个数的乘积
设$v_p(x)$表示质数$p$在$x$质因数分解中的指数大小，$M_p$表示所有$v_p(a_i)$的最大值，$m_p$所有$v_p(a_i)$的非严格次大值
考虑算出$M_p$在操作之后的改变值$\Delta M_p$
$$\Delta M_p=([v_p(r_i)=M_p]+[v_p(r_j)=M_p])(m_p-M_p)+\max (v_p(r_i+r_j)-M_p,0)$$
证明
当$[v_p(r_i)=M_p]=0,[v_p(r_j)=M_p]=0$时，显然满足
当$[v_p(r_i)=M_p]=1,[v_p(r_j)=M_p]=0$时，$v_p(r_i+r_j)=v_p(r_j)<M_p$，满足
当$[v_p(r_i)=M_p]=0,[v_p(r_j)=M_p]=1$时，与上种情况类似
当$[v_p(r_i)=M_p]=1,[v_p(r_j)=M_p]=1$时，$m_p=M_p$，满足
然后就能用$ntt$优化了