(来源：b站左程云up  099）

一：求逆元：

1）要保证a可以整除b      2)要保证mod的是一个质数        3）b和mod互质

题目2）3）一般都满足，主要是1)

方法：如求1.（10/5）%mod   mod=3

     5的逆元其实就等于（5的mod-2次方）%mod=5%3=2；然后用10%mod=1，结果就等于（分母的逆元乘以分子mod后的值）%mod，即(2*1)%3=2！

                  2.（18/6）%mod   mod=5

     先求6的逆元，就是6的3次方再mod，如果mod太大用快速幂，之后结果就为1；18%5=3；3*1=3！

求1-n的逆元，1的话易知就是1，然后就接着用公式：

a[i]=(int)(mod-a[mod%i] * (mod/i)%mod)

求阶乘的逆元：

//第一步，求1-n阶乘的mod：//1！%mod=1；然后用乘法同余：//2！%mod=(1!%mod)*(2%mod)%mod    ；  3！%mod=(2!%mod)*(3%mod)%mod........//把他们都存在一个数组里面，假设为b[N]；b[1]=1;
for(int i=2;i<=n;i++)
{b[i]=(i%mod)*(b[i-1]%mod)%mod;
}

第二步，可以直接套公式但比较慢：

快速幂：

int pow(int a,int b)
{int result=1;while(b){if(b&1){result=result*a%mod;b/=2;a=a*a%mod;}else{b/=2;a=a*a%mod;}}
return result;
}

//ps:0的逆元为1，因为0！=1；//所以就是：c[0]=1；c[0]=1;
for(int i=1;i<=n;i++)
{c[i]=pow(b[i],mod-2);
}

优化后：

所以由上面我们求Cnm，n! / ((n-m)!*m!)

而n!%mod 求出来了：b[n]

(n-m)!的逆元：c[n-m]，m!的逆元：c[m]

int answer(int n,int m)
{int ans=b[n];ans=(ans*c[m])%mod;ans=(ans*c[n-m])%mod;return ans;
}

二：容斥原理：

相当于：a U b U c  的话：

就等于：a+b+c-a∩b-b∩c-a∩c+a∩b∩c

而如果aUbUcUdUe:

dp[i]表示最大公约数为i的子序列个数

int DP()
{for(int i=n;i>=1;i--){int cn=0;for(int j=i;j<=n;j+=i){cn=(cn+d[j])%mod;}dp[i]=(pow[cn]-1+mod)%mod;for(int j=2*i;j<=n;j+=i){dp[i]=(dp[i]-dp[j]+mod)%mod;//减法求余加mod}}return dp[1];
}//2的0-n次方mod后的值
pow[0]=1;
for(int i=1;i<=n;i++)
{pow[i]=(pow[i-1]*2)%mod;
}//d[i]:i出现的次数for(int i=0;i<n;i++)
{cin>>r;d[r]++;
}