2022.1.13
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
UVA1391.Astronauts
首先前两种限制条件显然只能满足一种，那么三个条件对于每个宇航员来说，就只有两种选择，转化成了一个 \(\text{2-SAT}\) 问题。
P2398 GCD SUM
后面那个式子一眼欧拉反演，
\[\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)=\sum_{x=1}^{n}\sum_{j=1}^n\sum_{d|i,j} \varphi(d)=\sum_{d=1}^n\varphi(d) \lfloor \frac{n}{d} \rfloor^2
\]
CF285E.Positions in Permutations
一开始想这题，设的状态 \(f_{i,j,k=0/1,t=0/1}\) 表示考虑完前 \(i\) 个，有 \(j\) 个位置好，并且只在这些位置填数，\(i\) 和 \(i-1\) 是否被填的方案数。
转移方程如下
\[f_{i,j,0,0}=f_{i-1,j,0,0}+f_{i-1,j,1,0}+f_{i-1,j-1,0,0}
\]
\[f_{i,j,0,1}=f_{i-1,j-1,0,0}+f_{i-1,j-1,1,0}
\]
\[f_{i,j,1,0}=f_{i-1,j,0,1}+f_{i-1,j,1,1}+f_{i-1,j-1,0,1}
\]
\[f_{i,j,1,1}=f_{i-1,j-1,0,1}+f_{i-1,j-1,1,1}
\]
本来以为这样直接乘上 \((n-m)!\) 就是答案，但是其余随机放可能会出现新的好的位置。
但是我们这样做，表示钦定 \(k\) 个为好位置，其余随意的方案数，二项式反演一下就可以得出最后的答案了。
P7704 「MCOI-09」Greedy Deletion
答案显然就是出现次数为奇数的质数的贡献。
我们可以把询问离线下来，对于每个质数 \(p\) ，暴力考虑 \(p,p^2,p^3...\) 的倍数即可。
P8916 [DMOI-R2] 暗号
这题如果从子树的角度去考虑，可能很不容易做，但是我可以转换一下思路，考虑每一个点作为答案的贡献，假设一个点是黑色，那么贡献就是 \(1+\) 其祖先链上满足父节点和子节点都是黑色的点对的个数，白色同理。
考虑转移，初始 \(f_{i,j,k,t=0/1}=a_i\cdot((j+1)[t=0]+(k+1)[t=1])\) ，
\[f_{i,j,k,0}=f_{i,j,k,0}+\max(f_{x,j-1,k,0},f_{x,j,k,1})
\]
\[f_{i,j,k,1}=f_{i,j,k,1}+\max(f_{x,j,k-1,1},f_{x,j,k,0})
\]
当树形 \(DP\) 不好从子树转移时，可以考虑每个点在其父节点上的贡献和。