清北学堂Day3
卷积公式（Dirichlet卷积）
这个式子看上去就很变态，那么他是什么意思呢：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。就是说
函数f（x）和g（x）对于n的卷积等于n的每一个因子d在f(x)上的值乘上d/n在g(x)上的值的和
例:
设g(n)=φ(n),f(n)=n;
求（f*g）(12)=?;
时间复杂度的话，首先要枚举所有的因子o（sqrt(d) ，所以整个的时间复杂度就是o(n*sqrt(n))
有一个非常神奇的筛法
这个筛法其实和埃氏筛是差不多的，换了个写法而已，但是：
我们用这个循环方式的话，就可以改变时间复杂度
有一个很有意思的东西
1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...=logN；
ll f[N],g[N],h[N]; void calc(int n) { for(int i=1;i*i<=n;i++) { h[i*j]+=f[i]*g[i]; for(int j=i+1;i*j<=n;j++) h[i*j]+=f[i]*g[j]+f[j]*g[i]; } }
这样这个筛法的时间复杂度可以变成n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...)即o (n logN);
数论题目有一个很好的技巧，只要我们把循环的顺序换一下，很多时候时间复杂度就降下来了，而且数论题目很多也都是考的对算法的优化；很多时候公式推出来了，到最后优化写的不行就直接TLE，这是非常悲催的事情
[]表示如果为真返回1，否则返回0；
这样就能换成了对所有因子的莫比乌斯函数求值
再换一下，把d放在前面，就大大优化了
这里[ ]是向下取整，要注意不要和上面的判断真假混淆
这里运用了一个非常重要的思想，也就是分块，其实就是通过下取整的方式来把枚举的数字快速筛掉
其实看一下取整函数的图像就能很好发现
实际上n/[n/d]就是区间的右端点
代码实现
xian_xing_shai(); for (int a=1;a<=n;a++) sum_mu[a] = sum_mu[a-1] + mu[a]; int solve(int n,int m) { int ans=0; //for (int d=1;d<=n;d++) // ans += mu[d] * (n/d) * (m/d); for (int d=1;d<=n;) { int next_d = min( n/(n/d), m/(m/d) ); ans += (sum_mu[next_d] - sum_mu[d-1]) * (n/d) * (m/d); d=next_d+1; } return ans; }
组合数
取两册文字不同的书的方案=取日文英文+取日文中文+取英文中文
相同的：取日文日文，取中文中文，取英文英文
随便取两册：上两问加起来
考虑两面旗帜的方法和三盆花的方法，根据乘法原理乘起来即可
ans=P(5,2)*P(20,3)
先考虑对七名男生排序，然后在六个间隔中插入三名女生
ans=P(7,7)*P(6,3)
先看个位数：有0，2，4，6，8五种情况，对于0和8，它的千位数都是有2,3,4,5,6五种情况，对于剩下的三个数，各有2,3,4,5,6中除去它自己四种情况，故千位和个位可能的情况共有：2*5+4*3=22 种 ，然后对百位和十位排序，有P(8,2)种情况
故ans=22*P(8,2)
总的方案数减去选上男A和女B的方案数
ans=C(12,5)-C(10,3)
按余数分类：余数相同和余数不同
余数相同分为：(0,0,0),(1,1,1).(2,2,2);
1~300这些数中，余数相同的各有100个
故每一种可能的方式均为C(100,3)
余数不同时，每一个数都是从不同的余数中选一个，故方式为C(100,1)3
ans=3*C(100,3)+C(100,1)3
由于每种颜色的旗帜是相同的，所以讲相同颜色的旗帜放一起，只能算是一种方式
从0走到（n，m）是c（n+m，n）
变式
解决的方案是用所有方案减去不合法方案，不合法方案即为穿过了y=x这条线的走法，所以我们找到所有不合法方案穿过这条线的时刻，我们把它第一次不合法的位置的路线沿y=x对称，很容易发现，一定经过（1,0）
下面来点OI系列的
P4369 [Code+#4]组合数问题
运用对数计算法则，把组合数计算降级为加法运算，在o（1）的情况下比较出来大小
很容易知道最大的组合数一定是杨辉三角最大的一层的最中间的数，而次大的数一定是在最大树的周围四个当中。
Luogu 4370
利用杨辉三角进行展开，所以我们可以给出另外一个是式子
把c(n,m)展开k次之后可得到
斐波那契数列递归式用矩阵求解
Lucas定理：
容斥原理：
选择k个集合来交
当k是奇数，加上，是偶数的时候，减掉；
维恩图画出来，自然可以求解
首先我们知道y
最大也就是64，因此我们可以枚举y
很容易知道，y次根号下n就是最大循环到的
