[CF1007B]Pave the Parallelepiped[组合计数+状态压缩]

题意

\(t\) 组询问，给你 \(A, B, C\) ，问有多少组三元组 \((a, b, c)\) 满足他们任意排列后有： \(a|A,\ b|B,\ c|C\) 。

\(A,B,C,t\leq 10^5\)

分析

我们把三个数的所有因子用 \(2^3 - 1\) 个状态表示这个数是 \(A,B,C\) 中的哪几个数字的因子。
按照从小到大的顺序枚举3个数对应的集合，首先保证能够找到一种对应方式(每个数对应是谁的因子)，相同的数集利用插板法计算方案避免重复。

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cctype>

#include<vector>

#include<queue>

#define For(s) for(int s=1;s<8;s++)

using namespace std;

const int N=1e5 + 7;

typedef long long LL;

int n,T;

int sz[8],A[8],f[8],b[8]={0,1,1,2,1,2,2,3};

LL ans,tmp;

int gcd(int a,int b){

  if(!b) return a;

  return gcd(b,a%b);

}

int get(int x){

	int res=0;

	for(int i=1;i<=sqrt(x);i++)if(x%i==0){

	  res++;

	  if(i*i!=x) res++;

	}

	return res;

}

bool check(int a,int b,int c){

    if((a&1) && (b&2) && (c&4)

        return true;

    if((a&1) && (c&2) && (b&4))

        return true;

    if((b&1) && (a&2) && (c&4))

        return true;

    if((b&1) && (c&2) && (a&4))

        return true;

    if((c&1) && (a&2) && (b&4))

        return true;

    if((c&1) && (b&2) && (a&4))

        return true;

    return false;

}

LL C(int n,int m){

	if (m == 0) return 1;

	if (m == 1) return n;

	if (m == 2) return 1ll * n * (n - 1) / 2;

	if (m == 3) return 1ll * n * (n - 1) * (n - 2) / 6;

}

void work(){

	 scanf("%d%d%d",&A[0],&A[1],&A[2]);

	 ans=0; memset(sz,0,sizeof(sz));

	 memset(f,0,sizeof(f));

	 For(S){

	 	for(int i=0;i<3;i++) if(S>>i&1){

	 	  	if(!f[S]) f[S]=A[i];

	 	  	else f[S]=gcd(f[S],A[i]);

	 	}

	 	f[S]=get(f[S]);

	 }

	 For(s) For(S)if((S&s)==s){

	   	int cnt=b[S]-b[s];

	   	sz[s]+=f[S]*(cnt&1?-1:1);

	 }

	 For(s1)for(int s2=s1;s2<8;s2++)for(int s3=s2;s3<8;s3++){

	   if(check(s1,s2,s3)){

	   	  tmp=1;int cnt=1,cho=233;

	   	  if(s1==s2) cho=s1,cnt++;

	   	  if(s2==s3) cho=s2,cnt++;

	   	  if(s1^cho) tmp*=sz[s1];

	   	  if(s2^cho) tmp*=sz[s2];

	   	  if(s3^cho) tmp*=sz[s3];

	   	  if(cnt^1) tmp*=C(sz[cho]+cnt-1,cnt);

		  ans+=tmp;

	   }

	 }

	 printf("%lld\n",ans);

}

int main(){

	scanf("%d",&T);

	while(T--) work();

	return 0;

}

巴特西

[CF1007B]Pave the Parallelepiped[组合计数+状态压缩]

题意

分析

代码

最新文章

热门文章