ZROI #364. 【2018普转提day18专题】嘤嘤嘤

直接贴代码

具体见注释

#include<stdio.h>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<cmath>

#include<iostream>

#include<queue>

#include<string>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef long double ld;

typedef unsigned long long ull;

typedef pair<long long,long long> pll;

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)

#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)

ll read(){

	ll x=0,f=1;char c=getchar();

	while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

const int maxn=100100,maxm=55;

ll n,m,s,t;

ll tot[maxm][maxn],f[maxm][maxn][2];

ll a[maxn],q[maxn],lim,start;

ll dfs(int x,int y,int z,ll tmp=0){

	//当前确定了后x位，加的数是tmp时第x位上有y个数发生了进位，是否超过了限制lim（z=0/1)

	if(x==m) return !z;	//如果枚举完了，就看当前加的数是否可行

	if(f[x][y][z]!=-1) return f[x][y][z];

	ll nw=0;

	int a=tot[x][y],b=y-a,c=tot[x][n]-a,d=n-y-c;

	//a表示按照后x位排序后前y个数有几个第x+1位上是1，这时候a所代表的的数这一位为1且前一位发生了进位，那么这一位实际上会变成0

	//b表示有几个数发生了进位但是这一位不是1

	//c表示有几个数这一位是1但是没有进位，在当前情况下b和c代表的数是等价的

	//d表示剩余的数（既没进位也不是1）的个数

	int t=(s>>x)&1;	//t表示s的这一位是啥

	//现在有a+d个数这一位是0，b+c个数这一位是1

	if(((b+c)&1)==t) nw+=dfs(x+1,a,((lim>>x)&1)?0:z,tmp);	//这一位放0

	if(((a+d)&1)==t) nw+=dfs(x+1,a+b+c,((lim>>x)&1)?z:1,tmp+(1<<x));	//这一位放1

	return f[x][y][z]=nw;

}

ll solve(ll x){

	lim=x;

	memset(f,-1,sizeof(f));

	return dfs(0,0,0);

}

int main(){

	n=read(),m=read(),s=read(),t=read();

	rep(i,1,n){

		a[i]=read();

		start^=a[i];

	}

	rep(i,0,m-1){

		rep(j,1,n)

			tot[i][j]=tot[i][j-1]+((a[j]>>i)&1);

		int nums=0;

		rep(j,1,n)

			if((a[j]>>i)&1) q[++nums]=a[j];

		rep(j,1,n)

			if(!((a[j]>>i)&1)) q[++nums]=a[j];

		swap(a,q);

		//q表示原来的数按照后i+1位排序之后的结果

		//tot表示原来的数按照后i位排序之后，第i位上前j个数里有几个1

	}

	printf("%lld\n",solve((1ll<<m)-1)*(t>>m)+solve(t%(1ll<<m))-(start==s));

	return 0;

}

Review

为什么这么做？

首先按位考虑，这个很好想

然后我就没思路了

没有想到数位dp。。。

而且对于每个长度为j的后缀的处理很巧妙