周日爽爽爽???。
上午写了写 ds?，下午打了妈死 OJ 的 noip 模拟赛?。
妈的下午宿舍怎么他妈两点二十封楼啊?，傻逼吧我草，你他妈的之前不都是五十才封楼？服了我草???。没睡好，比赛补觉?。想 T1 的时候补了半个小时觉想到了 80pts 的 \(O(n^2)\) 做法?，T2 感觉很像上午做的一道题啊（赞赏），搞了个丹钓站搞搞就过了?。T3 很简单的 50pts 暴力?，T4 想了半天?。妈的场上降智了我草，我他妈以为边双的 dfs 树是一条链了，妈的。好像把我的做法换成树上差分就能过???。
我是傻逼。
好好好，写闲话的时候出分了：\(80+40+50+20\)，逆天?。T2 挂惨了???。
速报：T2 挂 60pts 原因：
ans = n * (n + 1) / 2;
n 是 int，最大 1e5
晚上就开始摆烂了?，距离退役还有 \(\sqrt 2\) 天???。这段时间要好好珍惜?。
今天好像又没啥逆天事情?。
我草 R&M 的第五季第十集好他妈牛逼，之前好多伏笔都解开了。
推歌：X.E.N.O -sasakure.UK
好听。
不是为啥我前两天选的题 l6t 都做过啊，卷王。
P3773
我们考虑这个序列的性质，即这些组合数中不能出现偶数。我们考虑如何利用这个性质。
我们把组合数的计算公式搬出来：\(\dbinom{n}{m}=\frac{n!}{m!(n-m)!}\)，为了让它为奇数，我们需要让上下阶乘的 \(2\) 的个数相等。
我们考虑把阶乘分解，设 \(f(x)\) 为 \(x!\) 所含的 \(2\) 的个数，则易得：
我们再设 \(g(x)=x\)，\(h(x)\) 为 \(x\) 二进制中 \(1\) 的个数，则
则 \(f(x)=g(x)-h(x)=x-h(x)\)。再根据需要让上下阶乘 \(2\) 的个数相等，能得出来 \(h(n)=h(m)+h(n-m)\)，即 \(n\) 二进制下 \(1\) 的个数等于 \(m\) 二进制下 \(1\) 的个数加 \(n-m\) 二进制下 \(1\) 的个数。我们考虑如何满足这个条件。
考虑 \(n=(\cdots 00100\cdots)_2, m=(\cdots 00010\cdots)_2\)，那么 \(n-m=(\cdots 00010\cdots)_2\)。显然不可能 \(1\) 的个数相等，因此我们必须满足 \(m\) 是 \(n\) 的子集。
这样就好做了。我们先把所有数存一下位置，从后往前扫，枚举 \(a_i\) 的子集，看是否在 \(i\) 后面，转移即可。
时间复杂度：\(O(\mathrm{能过} )\)。
今天闲话内容有点少?，多放点图吧?。
图图
