模型一：站队问题

元素优先法：特殊位置优先讨论

相邻捆绑法：小团体也是

定序按照无序算，或者看成其他元素确定，定序对方案数量没有影响

模型二：排队

插空法：

三个人8座位，每个人左右有空位：

空位5个，空间隔4个，三个人插里面，三个人各自有位置顺序

模型三：排数

注意0特殊位置，计算方案数要用位置（第一个位置放什么）

不能用数字（这个数字可以放什么位置），这样就混了

 排列组合算法

C combine

求有多少种长度为 n 的序列 A，满足以下条件： 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多，序列数对 10^9+7 取模。

const int N=1000000+10;
ll inv[N],mul[N],mul_inv[N],d[N];
int t,n,m;
void pre()
{
    mul[0]=mul_inv[0]=inv[0]=1;
    inv[1]=mul[1]=mul_inv[1]=1;
    _f(i,2,N)
    {
        mul[i]=mul[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        mul_inv[i]=mul_inv[i-1]*inv[i]%mod;
        //if(i<=4)chu("mulinv %d %lld\n",i,mul_inv[i]);
    }
    d[0]=1,d[1]=0,d[2]=1;
    _f(i,2,N)
    {
        d[i]=(i-1)*((d[i-1]+d[i-2])%mod)%mod;
    }
}
int main()
{
     t=re();
     pre();
     for(int i=1;i<=t;i++)
     {
         n=re(),m=re();
     //    chu("%lld %lld %lld %lld\n",mul_inv[n-m],mul_inv[m],mul[n],d[n-m]);
         chu("%lld\n",(((mul_inv[n-m]*mul[n])%mod*mul_inv[m])%mod*d[n-m]%mod)); 
     }

    return 0;
}
/*
预处理：线性求组合数（就是帅！），线性求逆元，线性求错位排序 
*/

 D

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值

还可以结合小根堆大根堆求方案数量！

f[i]=(f[i*2]*f[i*2+1]*C(siz[i],siz[i*2])) %p

综合各种方法吧，p一定是质数

数组下标二倍！细心啊

容斥原理

//多步容斥原理 ，在组合数ppt里，一堆加减的公式那个
int f[N]={1};
int c[4],d[4];
int ans;
//这里非常神奇啊
//就是对于递归到的每一个硬币，
/*
如果k=奇数，代表前面已经超限了奇数个，是应该减去的
如果算上这个硬币超限，就是偶数个，应该加，所以k+1,奇数变偶数
如果不算上，还是奇数个，递归传递下去
因为每一个硬币只有超限或不超限制两种情况，所以dfs可以覆盖所有 
当然笨拙一点也可以 
*/ 
void dfs(int x,int k,int now)
{
	if(now<0)return;//没钱了结束了
	if(x==4)// 
	{
		ans+=k&1?-f[now]:f[now];//
		return; 
	 } 
	 dfs(x+1,k+1,now-c[x]*(d[x]+1));//
	 dfs(x+1,k,now); 
}
int main()
{
	int i,j,t,s;
	
	_f(i,0,3)
	{
		_f(j,c[i],10000)
		{
			f[j]+=f[j-c[i]];//这个dp算方案数量的 
		}
	 } 
	//所有可能方案-一个超限的不合法硬币方案，减去重复了，再加上两两重复的，循环到最多个 
	 while(t--)
	 {
	 	_f(i,0,3)
	 	d[i]=re();
	 	s=re();
	 	ans=0;
	 	dfs(0,0,s);
	 	chu("%d",ans);
	 
	 }
    return 0;
}

　　E集合计数

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）

容斥原理，交集元素个数是k，把k固定，剩下(n-k)个元素有a=2^(n-k)集合数,从中任意取，每个集合都可以取或者不，

但不能都不取出来，因此有2^a-1种取法，C（n,k）*（2^a-1）是答案？no！

还要去除交集是k+1,k+2,k+3.....的方案数，+（所有交集是k+1）的方案数-(所有交集是k+2)的方案数

这里就看成在n-k个元素的基础上进行就可以，C（n-k，i）*(取i个方案数)

二的次幂怎么办？f(i)=2^(2^i)-1,发现f(i)=f(i-1)*f(i-1)+f(i-1)*2;f[0]=1

线性递推解决吧！

F. 牡牛和牝牛

排列组合，可重复计数原理：
相当于 0 1序列排序，每个0之间必须有至少k个1
先固定找出必须的1，设有x个0（0决定了1），至少有k(x-1)个1
剩下n-k(x-1)-x个必须是1了
a=x+1个0的空隙里插入b=n-k(x-1)-x个1
抽象！
b个无序球放入a个有序盒子里
法一：从a+b-1个数字里挑出b个
C(a+b-1,b)
法二：隔板法
b个球插入a-1个隔板,a+b-1个位置插入b个隔板
C(a+b-1,b)

排列组合、crt、费马小定理，容斥原理，lucas定理，组合数取模 - 比赛 - 衡中OI (hszxoj.com)

G.小小的优化

1 for example
2 _f(i,1,n)
3 {ans+=C(t+i,t);}
4 printf("%d",ans);
5 当n>=1e6基本超时
6 把原式子+C（n+1,n+1）
7 C(t+1,t+1)+C(t+1,t)=C(t+2,t+1)
8 C(t+2,t+1)+C(t+2,t)=C(t+3,t+1)
9 得到答案是C(t+n+1,t+1)