最近把kzf、小狗的课件什么的都过了一下，复习了组合数学，看了两篇论文，然后准备开推鸿少给的题和其他的一些题。

乱入：话说罗大神终于要回来虐我们了真是TATQAQ2333！

BZOJ1968约数研究：只要统计每个数是多少个数的约数即可

BZOJ1211树的计数：直接搞prufer数列，因为每个节点在数列中出现di-1次。然后直接暴力枚举prufer数列个数，但是要注意特判无解。

BZOJ1005明明的烦恼：之前看的时候觉得好神，其实跟上题是一样的，直接搞prufer数列，反正已知的结点必须在数列中di-1次，然后其余部分就随便了，组合数搞搞就出来了。

BZOJ1485有趣的数列：《组合数学》原题，直接上Catalan数列。话说算答案的时候要加特技，先线性筛一下，统计出每个数的最小质因数是哪个，然后将每个合数的系数下传，细节看代码。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define N 2000050
ll ans=1,n,m;
int c[N],p[N],ss=0,v[N];
inline ll Quick_mi(ll x,int y)
 {
 	ll z=1;
 	while (y)
 	 {
 	 	if (y&1) z=(z*x)%m;
 	 	x=(x*x)%m;
 	 	y/=2;
 	 }
 	return z;
 }
int main()
 {
    int i,j,k,l,q,w,e;
    memset(c,0,sizeof(c));memset(v,0,sizeof(v));
    memset(p,0,sizeof(p));
    scanf("%d%d",&n,&m);
    for (i=2;i<=n << 1;i++)
     {
     	if (!v[i]) p[++ss]=i;
     	for (j=1;j<=ss;j++)
     	 {
     	 	if (p[j]*i>n << 1) break;
     	 	v[p[j]*i]=p[j];
     	 	if (i%p[j]==0) break;
     	 }
     }
    for (i=2;i<=n;i++) c[i]=-1;
    for (i=n+2;i<=n << 1;i++) c[i]=1;
    for (i=n << 1;i>=2;i--)
     if (!v[i])
       ans=ans*Quick_mi(i,c[i])%m;else
       c[v[i]]+=c[i],c[i/v[i]]+=c[i];
    printf("%lld\n",ans);
    return 0;
 }

BZOJ2425计数：这题只要从高位到低位一路扫过去就可以了，因为上界对答案是造成了影响的，所以只要对于每一位统计这一位不取上界并且前面几位都取了上界的答案数，只要记下还有哪些数字没用过，这个用组合数很容易统计。

BZOJ2431逆序对数列：很容易可以得到递推式，设ai,j为i个数j个逆序对的数列，个数就是上一行的j-i+1~j个数的和，这个可以通过ai,j-1消西格玛，然后n和m只有1000，所以O(nm)的递推可以直接出答案。

BZOJ2729排队：完全就是《组合数学》第二章的题，随便算算。

BZOJ2751容易题：设si为前i个数的数列的乘积和，则si+1=si*第i个数的可取的数的和，但是由于n太大了，所以可以对于有限制的数单独算，其余的数直接快速幂统计。

BZOJ3209花神的数论题：水过，也是从高位到低位统计出现1的次数为i的数的个数，最后快速幂乘起来

BZOJ2705Longge的问题：发现就是要我们求Σ(i|n) i*φ(n/i)，然后枚举n的因子i，算φ甚至sqrt(n)都不用，因为n已经因式分解过了，所以直接枚举n的因子算φ。

BZOJ2956模积和：看起来好神，然后随手点开记录发现了第一版的HJWJBSR在3月的记录，顿时吓傻，然后马上想起来当时这题是LAccelerator叫我做的，记得当时想了好久，还被罗大神D了。于是想了想感觉确实不算难：把模化去变成ΣΣ(n-i*[n/i])*(m-j*[m/j])=(nm)^2-n^2Σi[m/i]-m^2Σi[n/i]+ΣΣij[n/i][m/j]，第二项第三项可以通过分块计算n/i然后用前缀和去乘最后加起来就可以了，话说第四项就是第二项第三项的积啊。补：话说好像还有i!=j这个限制于是减去就好了，但是这样好像还是要分块搞，还要用到什么平方和公式的= =真是hentai

BZOJ2242计算器：第一问快速幂，第二问直接移项所以还是快速幂（我还想什么扩展欧几里得真是羞耻），第三问BSGS。

BZOJ2173整数的lqp拆分：直接打表找规律= =

BZOJ2301Problem b：化简式子，线性筛出莫比乌斯函数前缀和，然后貌似就可以分块做了。

BZOJ1004Cards：直接套Burnside引理，DP求中间值。

BZOJ2463谁能赢呢？：可以发现棋盘可以多米诺骨牌覆盖的时候就先手必胜，否则后手必胜。因为先手总要从多米诺骨牌一端走到另一端。所以直接判奇偶。