# 二项式反演，莫比乌斯反演。

xiaoxiao2021-02-28  12

1、设出两个函数，f(i),g(i)。

g(n)=sigm(i=0到i=n)C(n,i)*(-1)^(n-i)f(i)

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封信装错信封

#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

(1 ≤ n, m ≤ 1e9 , 1 ≤ k ≤ 1e6 , k ≤ n, m)