1、设出两个函数，f(i),g(i)。
要求其满足条件f(n)=sigm(i=0到i=n)C(n,i)g(i)
然后根据这个条件，可以推导出
g(n)=sigm(i=0到i=n)C(n,i)*(-1)^(n-i)f(i)
意思是得出了一个函数可以求出另外一个函数
莫比乌斯反演，O(N)求法
const int N = 1e6 + 5; int mu[N], vis[N], prime[N]; int tot;//用来记录prime的个数 void init(){ mu[1] = 1; for(int i = 2; i < N; i ++){ if(!vis[i]){ prime[tot ++] = i; mu[i] = -1; } for(int j = 0; j < tot && i * prime[j] < N; j ++){ vis[i * prime[j]] = 1; if(i % prime[j]) mu[i * prime[j]] = -mu[i]; else{ mu[i * prime[j]] = 0; break; } } } }例子：
HDU1465
设g(i)表示正好有i封信装错信封
那么sigmC(n,i)*g(i) 就为将n个信封装入的所有可能数量。
令其为f(n)=n!; 因为正好这么令f(i)是满足条件的
那么g(n)=sigm(i=0到i=n)C(n,i)*(-1)^(n-i)f(i)
那么求出g(n)即可
#include <iostream> #include <iomanip> #include <stdio.h> #include <string.h> #include <stack> #include <map> #include <vector> #include <algorithm> #include <set> #include <queue> #include <math.h> using namespace std; const int MOD=1e9+7; long long f[50]; int init(){ memset(f,0,sizeof(f)); f[0]=1; for(int i=1;i<=20;i++){ f[i]=i*f[i-1]; } } int main(){ freopen("in.txt","r",stdin); // freopen("out1.txt","w",stdout); int t1,t2,t3,t4,n,m,i,j,k,f1,f2,f3,f4; int l,r,c,x,y,num; int T; init(); long long g1,g2,g3; int ans; while(scanf("%d",&n)==1){ ans=pow(-1,n); g1=0; for(i=0;i<=n;i++){ g1+=ans*f[n]/f[n-i]; ans=-ans; } cout << g1<< endl; } return 0; }UVALive 7040
题意：给n盆花涂色，从m种颜色中选取k种颜色涂，保证正好用上k种颜色，你必须用上这k种颜色去涂满n个相邻的花，并且要求相邻花的颜色不同，求方案数。
(1 ≤ n, m ≤ 1e9 , 1 ≤ k ≤ 1e6 , k ≤ n, m)
首先找出满足二项式反演的f(i)与g(i)令g(i)为准确用i种颜色把花盆全部涂满的方法。
令f(i)为用i种颜色把花盆全部涂满的方法。
那么对于k种颜色，涂花的方法数有k*(n-1)^(k-1)
此时f(n)=sigm(i=2到i=n)C(n,i)g(i)=k*(n-1)^(k-1)
那么g(n)=sigm(i=2到i=n)C(n,i)*f(i)*(-1)^(n-i)
此时要求的就是C(m,k)g(k)
