hdu 3929 Big Coefficients (递归形式的容斥原理+lucas定理的结论)

Mar 3, 2016 · 1 min read · lucas定理容斥原理

题意：F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am，求系数是奇数的项的个数。思路：解题报告涉及到的由lucas定理得到的推论的证明lucas定理证明以及这篇理解里有递归形式的容斥定理的一般写法。。递归形式的容斥定理

dfs(int beg,set S,int sym)
{
     ans+=num(S)*sym;
     for(int i=beg;i<=n;i++)
         dfs(i,S∩A[i],sym*-1);
}

for(int i=1;i<=n;i++)
     dfs(i,A[i],1);

第一次接触递归形式的容斥定理...还不是特别理解，据说要比循环的写法少一层msk(应该是少一个1</* *********************************************** Author :111qqz Created Time :2016年03月03日星期四 18时55分21秒 File Name :code/hdu/3929.cpp ************************************************ */

#include #include #include #include #include #include #include #include #include #include #include #include #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair

using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=20; int n; LL x[N],ans; LL getbit(LL x) { LL res = 0LL; while (x) { x=x&(x-1); res++; } return res; }

void dfs(int id,LL msk,LL f) { ans +=(1LL<<getbit(msk))f; for ( LL i = id+1 ; i < n ; i++) dfs(i,msk&x[i],-2f); }

int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif

// ios::sync_with_stdio(false); int T; int cas = 0 ; cin>>T; while (T--) { cin>>n; for ( int i = 0 ; i < n ; i++) scanf("%lld",&x[i]);

    ans = 0LL;
    for ( int i = 0 ; i < n ; i++)
    {
	dfs(i,x[i],1);

// cout<<"ans:"<<ans<<endl; }

    printf("Case #%d: %lld\n",++cas,ans);
    

}

#ifndef ONLINE_JUDGE
fclose(stdin); #endif return 0; }