【BJOI2014】欧拉

x=pikix=\prod p_i^{k_i},则 ϕ(x)=piki1(pi1)\phi(x)=\prod p_i^{k_i-1}(p_i-1),前边一部分指数可能为0,所以枚举 yy 的因数找出所有可能的 pi1p_i-1,然后把所有 pip_i 从大到小排序(为了尽快找到交优解)后 dfs 即可。

Read more »

AT3981

发现与 1 直接比赛的实际上有 n 组人中的最小值,每组分别有 202^02n12^{n-1} 个人并且在原序列上连续,考虑如果我们算出了每组的成员以及顺序的方案数,那么把 1 放在每个位置上都能唯一的确定这些组怎么放,于是将方案数乘上 nn 就是答案。

Read more »

AT4352

考虑容斥,答案就是 SE(1)Sf(S)\sum_{S \in E} (-1)^{|S|}f(S)

其中 f(S)f(S),是对于断开 S 后的所有联通块内随便配对的方案数。

Read more »

CF68D

可以发现只有 hqhq 级别的点被增加过权制,于是我们可以开一个 map 记录每棵子树的权值和。

Read more »
0%