链接：CF388D

题目大意

给定一个数\(n\)，求选择\(0 \sim n\)中任意个数的数字组成的集合\(S\)中，有多少满足若\(a\in S,b\in S\),则\(a \bigoplus b \in S\),输出方案数对\(1e9+7\)取模。

题目分析

设\(f[i][j][k]\)表示从第\(i\)位到最高位，已经选了\(j\)个基，且由基\(\bigoplus\)得到的最大值与\(n\)的差值是否在\(2^i\)以内的方案数。

况一：当\(k=0\)（异或最大值\(+2^i<n\)）时，考虑第\(i-1\)位。

如果该位要作为单独一个基，那么有\(f[i-1][j+1][0]+=f[i][j][0]\)，

该位单独作基，则新增情况数为之前有的情况，视为在之前每种情况上\(x\)新增一个\(2^{i-1} \)的基，

由设可保证新构成的集合异或最大值与\(n\)的差值在\(2^{i-1}\)之外，所以算在\(f[i-1][j+1][0]\)中。

如果该位不单独作基，而是放入已经拥有的j个基中，

那么对于每个基，都有放与不放两种选择，共\(2^j\)种，\(f[i-1][j][0]+=2^j*f[i][j][0]\)。

况二：当\(k=1\)（异或最大值\(+2^i>=n\)）时，考虑第\(i-1\)位。

讨论\(n\)在第\(i-1\)位是否为\(1\)：

1、\(n\)在第\(i-1\)位不为\(1\)，异或最大值\(+2^{i-1}>n\)：

此时最大值无法新增一个\(2^{i-1}\)。

那么，我们只能继承令第\(i-1\)位为偶数个\(1\)的情况，因为只有这样，最大值才不会改变，共\(2^{j-1}\)种。

2、\(n\)在第\(i-1\)位为\(1\)，异或最大值\(+2^{i-1}≤n\)：

如果在第\(i-1\)位取\(0\)，那么新得到的集合异或最大值\(+2^{i-1}≤n\)，因此应存入\(f[i-1][j][0]\)中，共\(2^{j-1}\)种。

如果在第\(i-1\)位取\(1\)，那么新得到的集合异或最大值\(+2^{i-1}≥n\)，因此应存入\(f[i-1][?][1]\)中。

对于第\(i-1\)位单独作基的情况，可以有\(f[i][j][1]\)种，存入\(f[i-1][j+1][1]\)中,\(f[i-1][j+1][1]+=f[i][j][1]\)。
对于第\(i-1\)位不单独作基的情况，可以对每个基选择放与不放，且必须放奇数个，共\(2^{j-1}\)种选择，

因此\(f[i-1][j][1]+=2^{j-1}*f[i][j][1]\)。

注意：

对于所有情况，当\(j=0\),对于选择第\(i-1\)位为\(0\)的情况，\(2^{j-1}\)算作\(1\)；

对于选择第\(i-1\)位为\(1\)的情况，\(2^{j-1}\)算作\(0\)，因为就算你没有选择一个基，你的异或和仍可以视作\(0\)。

代码实现

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#define MAXN 0x7fffffff

typedef long long LL;

const int mod=1e9+7;

using namespace std;

inline int Getint(){

	register int x=0,f=1;

	register char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-'0';

		ch=getchar();

	}

	return x*f;

}

int ans,f[35][35][2];

void Add(int &x,int y){x=((x+y>=mod)?(x+y-mod):(x+y));}

int main(){

	int n=Getint();

	f[30][0][1]=1;

	for(int i=30;i>0;i--)

		for(int j=0;j<=30;j++){

			Add(f[i-1][j][0],(1LL<<j)*f[i][j][0]%mod);

			Add(f[i-1][j+1][0],f[i][j][0]);

			int x=j?(1<<(j-1)):1,y=j?(1<<(j-1)):0;

			if(n>>(i-1)&1){

				Add(f[i-1][j][0],(LL)x*f[i][j][1]%mod);

				Add(f[i-1][j][1],(LL)y*f[i][j][1]%mod);

				Add(f[i-1][j+1][1],f[i][j][1]);

			}else Add(f[i-1][j][1],(LL)x*f[i][j][1]%mod);

		}

	for(int i=0;i<=30;i++)

		Add(ans,f[0][i][0]),Add(ans,f[0][i][1]);

	cout<<ans;

	return 0;

}

巴特西

Codeforces 388D Fox and Perfect Sets

题目大意

题目分析

代码实现

最新文章

热门文章