首页 > 代码库 > 编程之美初赛第二场 集合

编程之美初赛第二场 集合

2024-07-05 20:22:24   227人阅读

题目3 : 集合

时间限制:12000ms
单点时限:6000ms
内存限制:256MB

描述

统计满足下列条件的集合对(A, B)的数量：

  • A,B都是{1, 2, …, N}的子集；

  • A,B没有公共的元素；

  • f(A)<= f(B)。f(S)定义为S中所有元素的按位异或和。例如， f({}) = 0, f({1, 3}) = 2。

因为答案可能很大，你只需要求出它除以M的余数。


输入

第一行一个整数T (1 ≤ T ≤ 10)，表示数据组数。

接下来是T组输入数据，测试数据之间没有空行。

每组数据格式如下：

仅一行，2个整数N和M (1 ≤ M ≤ 108)。


输出

对每组数据，先输出“Case x: ”，然后接一个整数，表示所求的结果。


数据范围

小数据：1 ≤ N ≤ 20

大数据：1 ≤ N < 212



样例输入
1
3 100000000
样例输出
Case 1: 18
这题最开始想到的方法是位运算，每位代表一个数，当i&j==0时说明没有交集，然后进行f函数比较，但是时间消耗还是很多，N=16时就已经满足不了要求了。。。。后来尝试使用动态规划，数学推算出了h(n)=h(n-1)+3^(n-1)+count(n)，其中count(n)为取n这个数字时，n与所有{1..n-1}的子集组合进行比较，相等的个数。这里面count(2^k）会为0，这样再使用迭代，程序运行的会更加快点，但还是卡在N=17上超时了。。这里是没有使用openmp多线程的情况下，也没有使用分布式多线程来做。在数据结构上使用的是unsigned long long，这已经是C语言能表达的最大位数了，但是对N=2^20时，构成的排列2^N时，已经放不下了。。。这个不知怎么解决。。。


#include <stdio.h>
#define LONG unsigned long long

int f(int n,int total)
{
	int r=0,i=0,j=0;

	for (i=1,j=1;j<total+1;j++,i=i<<1)
	{
		if ((n&i)!=0)
		{
			r^=j;
		}
	}
	//printf("f %d--%d\n",n,r);
	return r;
}

LONG mypow(int a, int n)
{
	int i;
	LONG res = 1;
	for (i = 0; i < n; ++i)
	{
		res *= a;
	}

	return res;
}

int main(void)
{
	int T=0,num=0,N,M;

	LONG i,j,count,upper;
	scanf("%d",&T);
	getchar();

	while(num<T)
	{
		scanf("%d %d",&N,&M);

		count = 1;
		upper = mypow(2, N);
		//printf("upper:%ld\n",upper);
		
		for (i = 0; i < upper-1; ++i)
		{
			for (j = i+1; j < upper; ++j)
			{
				if ((i&j) == 0)
				{
					if (f(i,N)!= f(j,N))
						count++;
					else
						count+=2;

					if (count >= M)
					{
						count -= M;
					}
				}
			}
		}
		printf("Case %d: count:%d\n",++num,count);
	}
	return 0;
}

#include <stdio.h>
#define LONG unsigned long long

LONG f(LONG n,LONG total)
{
	LONG r=0,i=0,j=0;

	for (i=1,j=1; j<total+1; j++,i=i<<1)
	{
		if ((n&i)!=0)
		{
			r^=j;
		}
	}
	//printf("f %lld--%lld\n",n,r);
	return r;
}

LONG muti_mod(LONG a,LONG b,LONG MOD)//(a*b)mod MOD
{
	a%=MOD;
	b%=MOD;

	LONG ret=0;
	while (b)//fast mul
	{
		if (b&1)//a*b=a+a(b-1)
		{
			ret+=a;//ret = (ret + a)%c
			if (ret>=MOD)
				ret-=MOD;
		}
		//a*b=a*2 *b/2
		b>>=1;
		a<<=1;
		if (a>=MOD)
			a-=MOD;
	}
	return ret;
}

LONG mypow(LONG a, LONG n,int flag, LONG mod)
{
	LONG i;
	LONG res = a;
	if(flag==0)
		for(i=0; i<n-1; i++)
			res=res*a;
	else
		for(i=0; i<n-1; i++)
			res=muti_mod(res,a,mod);
	return res;
}

LONG jihe(LONG n, LONG mod)
{
	LONG i=0,j=0,p,upper,k,t=0,count=0,total=0;

	if(n==1)
		return 2;

	for(k=2; k<=n; k++)
	{
		p=1<<(k-1);
		upper = mypow(2, k-1,0,mod);
		if((k&(k-1))!=0)//n=2^n,count=0
		{
			for(i=0; i<upper; i++)
			{
				t=i|p;
				for(j=0; j<upper; j++)
				{
					if(((t&j)==0)&&(f(t,k)==f(j,k)))
						count++;
				}
			}
			count=count%mod;
		}
		//printf("k:%lld\t count:%lld\n",k,count);
		count=count%mod;
	}
	
	// (a / b) % m = ( a % (m*b)) / b  
	total=(mypow(3,n,1,2*mod)-1)>>1;
	//printf("total %lld\n",total);
	//printf("count %lld\n",count);
	return (1+total+count)%mod;//
}

int main(void)
{
	unsigned int T=0,num=0,N,M;
	LONG count;

	scanf("%d",&T);
	getchar();

	while(num<T)
	{
		scanf("%d %d",&N,&M);

		count=jihe(N,M);
		printf("Case %d: count:%lld\n",++num,count);
	}
	return 0;
}


联系
我们