蒟蒻来补一下数学
容斥原理
似乎从来不会用QAQ
BZOJ3198: [Sdoi2013]spring
考虑容斥原理计算恰好有k个相同的对数。
那么先计算至少有k个（其他并不知道相不相同）相同，那么我们发现有的有k+1个相同而我们不但计算上了它而且还算了C（k+1，k）次。
所以减去。然后发现我们减多了？有些有k+2个相同的，多减了C（k+2，k）次（因为每个恰好会被看做两个k+1个相同的），然后加回来C（k+2，k）*C（k，k）次，然后发现加多了，有些k+3个相同的多加了C（k+3，k+1）次（因为每个恰好会被看做两个k+2个相同的），然后减去C（k+3，k+1）*C（k+1，k）次。然后继续。。。
这里需要明确的一点是至少有k个相同的方案数：
显然这里的至少有k个相同并不是准确计数。因为有可能有重复计算。
如果是准确计数的话直接用至少k个相同减去至少k+1个相同就好了。
所以计算的时候要注意是准确的还是可能重复的。
QAQ并不是很好理解
BZOJ2839: 集合计数
领悟了新技能：炫酷反演魔术
我们令 $$f[n]=\sum_{i=0}^{n}\binom{n}{i}*g[i]$$
那么由二项式反演有
$$g[n]=\sum_{i=0}^{n}(-1)^{n-i}*\binom{n}{i}*f[i]$$
那么在此题中，很容易想到f[n]为2^n个集合随便选，至少选一个的方案数。
而g[n]就表示2^n个集合，随便选，至少选一个，然后交集为空的方案数。
那么我们只要知道g[n-k]就可以了。乘以一个组合数妥妥的。
当然列出式子我们发现是个卷积，那么如果对于K=1-n输出答案，我们用FFT卷积一下就好了。
然而这题也可以用容斥的思想考虑（其实上面就是和容斥推出了一样的式子，只是看起来更简单）
首先保证有k个交集，然后发现有的有k+1个相同的，而且被计算了C（k+1，k）次，那么减去。然后发现减多了，再加上C（k+2,k）*C（k，k）次。
然后又减去C（k+3，k+1）*C（k+1，k）。。。一直算下去。
BZOJ3622: 已经没有什么好害怕的了
这题其实很简单。
这题比较麻烦的是，选出k个数，k个数的选法和方案数有关系。
所以不能直接组合数算ans。
那么我们就考虑DP。
f[i][j]表示前i个糖果，至少选出j个糖果>药片的合法数。（当然要预先排序）
那么有递推式：
$$f[i][j]=f[i-1][j]+f[i-1][j-1]*(k-(j-1))$$
其中b[k]<a[i]而b[k+1]>a[k]。
这是很显然的。
而计算完之后我们还要对每个f[i][j]乘以n-j的阶乘。因为剩下的并不确定。
然后考虑容斥原理。
我们加上至少k个的f[n][k]，然而有一些 k+1个合法的，我们不但记上了它，而且每一种方案都记了C（k+1，k）次
所以减去f[n][k+1]*C(k+1,k)。然后我们又减多了，有一些k+2个合法的，每一种方案又会多加了C（k+2，k）*C（k，k）次。
然后加多了，有k+3个合法的，每个对应着C（k+3，k+1）个被重复计算了一次的k+1的集合，所以我们减去这些的贡献C（k+3，k+1）*C（k+1，k）。
然后继续。。。
所以最后的ans就是
$$ans=\sum_{i=k}^{n}(-1)^{i-k}*\binom{i}{k}*f[n][i]$$
当然这里的k是实际上应该有多个大的，而不是多了多少个大的。
数论
BZOJ3309: DZY Loves Math
烂大街的推导就不说了。然后发现我们需要O（n）求出 $$g[n]=\sum_{d|n}f[d]*μ[\frac{n}{d}]$$
然后翻当年题解发现我说“随便yy一下就好了”，然而现在yy不出来了
于是去膜拜了 Mektpoy 的题解。 Orz
值得记住的一点就是从一个n个元素的集合中取出偶数个元素的总方案数和奇数个元素的总方案数是相同的。
这是因为 $$\sum_{i=1}^{n}(-1)^i*\binom{n}{i}=(1+(-1))^n=0$$
BZOJ3560: DZY Loves Math V
这题首先一个很重要的转化就是$\phi(n)$是积性函数。所以我们可以对每个素数分开考虑。
不妨认为i素数的答案是$f[i]$，那么$$ans=\prod_{i是素数}(1+f[i])$$
+1是因为代表着不算这个素数。
然后接下来我们要考虑计算$f[i]$,不妨认为$a[i]$中素数$i$的幂为$b[i]$。
那么$$f[n]=\sum_{i1=1}^{b[1]}\sum_{i2=1}^{b[2]}\dots\sum_{in=1}^{b[n]}p^{\sum_{j=1}^{n}i_j}$$
其实这个问题和上面的化归过程差不多。
假设我们现在已经得到了前n个数选幂的所有情况的$p^i$不妨记为$ans$，那么只要让$ans*=\sum_{i=0}^{p^{b[n]}}$就得到了前n+1个数选所有幂的情况的$p^i$的乘积。
而后面那个和式其实是一个等比数列，我们直接上公式$$1+p^1+p^2+\dots+p^n=\frac{p^{n+1}-1}{p-1}$$即可。
然后这题就做完了
BZOJ3561: DZY Loves Math VI
直接爆上推公式！假设n<=m
$$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)^{gcd(i,j)}$$
枚举$d=gcd(i,j)$
$$=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)==1](\frac{i*j*d*d}{d})^d$$
莫比乌斯反演！
$$=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{k|i且k|j}μ(k)(\frac{i*j*d*d}{d})^d$$
把整除这种东西提到前面！
$$=\sum_{d=1}^{n}\sum_{k=1}^{\frac{n}{d}}μ(k)\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{m}{dk}}（\frac{i*j*k*k*d*d}{d}）^d$$
$$=\sum_{d=1}^{n}\sum_{k=1}^{\frac{n}{d}}μ(k)\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{m}{dk}}（i*j*k*k*d）^d$$
把和只和d有关的提出来，只和k有关的也提出来
$$=\sum_{d=1}^{n}d^d\sum_{k=1}^{\frac{n}{d}}μ(k)*k^d*k^d\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{m}{dk}}(i*j)^d$$
可以把后面的东西拆开！
$$=\sum_{d=1}^{n}d^d\sum_{k=1}^{\frac{n}{d}}μ(k)*k^d*k^d\sum_{i=1}^{\frac{n}{dk}}i^d\sum_{j=1}^{\frac{m}{dk}}j^d$$
我们发现，前面两重循环的复杂度是$O（nlogn）$的。
如果后面那一坨可以$O（1）$可以计算出来，那我们的问题就得到了解决。
考虑预处理前$i$个正整数的$d$次幂，那么我们是按d从小到大枚举的，而且有用的每次只有$O(\frac{m}{d})$项，所以每次再UPD一下这个数组好了！
总复杂度$O(nlogn)$
评论 (0)
