组合数的奇偶判定

组合数的奇偶判定在之前做过的题目里面，出现了很多关于杨辉三角的题目，很多时候都会联系到组合数的性质看。这里就来说明如何判断组合数的奇偶并证明。我们知道组合数可以表示为$$C_nm=\frac{n!}{m!(n-m)!}$$现在假设$n!,m!,(n-m)!的2的因子个数分别为A,B,C$。显然组合数

数论模板

我的数论模板最大公因数 int gcd(int a,int b) { return b>0?gcd(b,a%b):a; }扩展欧几里得 int exgcd(int a,int b,long long &d,long long &x,long long &y) { if(

类欧几里得模板

类欧几里得模板存个类欧几里德模板，想看看原理就看看敦哥(洪华敦)的教程敦哥无敌ll inv2=qpow(2,mod-2);ll sum(ll a,ll b,ll c,ll n){if(!a) return 0;ll x,y;if(a>=c||b>=c){x=sum(a%c,b%c,c,n

FFT,NTT,FWT模板

-------------"<<T<<endl;int len=2;for(i=1;(1<<i)<(n+m-1);i++)len<<=1;getrev(i);solve('P',len,n,m);solve('S',len,n,m);s

HDU3949 XOR（线性基）

HDU3949 XOR(线性基)题目：给你$n$个数，从其中随便取任意数问你第$k$小的异或和是多少。题解：这题是线性基的应用之一。我们知道一个集合的线性基可以异或出这个集合的所有异或和，并且方法唯一。对于一个数x能否被异或出来，我们可以这样做，假设x的最高位为r，那么在线性基里面找到最高为也为r的

Blocks(组合数学——生成函数)

Blockshttps://cn.vjudge.net/problem/POJ-3734题意：一排有n块砖，每块砖可以染成A,B,C,D四种颜色的其中一种，现在问你A颜色砖块有偶数个，B颜色砖块有偶数个的染色方法有几种？题解：这题虽然可以用矩阵快速幂的方法做，但也存在一种能秒杀这题的方法———生成函

51nod 1244莫比乌斯函数之和(杜教筛)

51nod 1244莫比乌斯函数之和(杜教筛)传送门题意：求$\sum_^\mu{(i)}$题解：这题就是求积性函数前缀和，一道杜教筛的模板题。公式推导如下：假设$\phi{(n)}=\sum_\mu{(i)}$我们知道有$$\sum_{d|i}{\mu{(d)}}=[n==1]$$我们可以把上面的