BZOJ 4513 [SDOI2016]储能表

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4513

题意：略。

思路：异或考虑二进制分解，可以考虑统计 $i\ xor\ j>k$ 的个数和异或和，我们就可以直接计算出答案，从高位到低位考虑进行数位 $DP$ ，设 $f[x][a][b][c]$ , $g[x][a][b][c]$ 为考虑前 $x$ 位， $i<n$ , $j<m$ , $i$ , $j$ 大于 $k$ 的方案数和异或和，然后去转移就可以了，最后的答案就是 $g[0][0][0][0]-kf[0][0][0][0]$ 。

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
	x=0;int f=0;char ch=getchar();
	while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x=f?-x:x;
}
int T,i,a,b,c,x,y,p,f[62][2][2][2],g[62][2][2][2];
ll n,m,k,table[62];
void up(int&a,int b){a+=b;if(a>=p)a-=p;}
int main(){
	for (read(T);T--;){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		read(n),read(m),read(k),read(p);
		for (table[0]=i=1;i<62;i++) table[i]=(table[i-1]<<1)%p;
		f[61][1][1][1]=1;
		for (i=60;i>=0;i--) for (a=0;a<2;a++) for (b=0;b<2;b++) for (c=0;c<2;c++) if (f[i+1][a][b][c]){
			int pn=(n>>i)&1,pm=(m>>i)&1,pk=(k>>i)&1;
			for (x=0;x<=(a?pn:1);x++) for (y=0;y<=(b?pm:1);y++){
				int d=x^y;
				if (c && d<pk) continue;
				up(f[i][a && x==pn][b && y==pm][c && d==pk],f[i+1][a][b][c]);
				up(g[i][a && x==pn][b && y==pm][c && d==pk],g[i+1][a][b][c]);
				if (d) up(g[i][a && x==pn][b && y==pm][c && d==pk],table[i]*f[i+1][a][b][c]%p);
			}
		}
		int res=0;k%=p;
		up(res,((g[0][0][0][0]-k*f[0][0][0][0]%p)%p+p)%p);
		printf("%d\n",res);
	}
	return 0;
}

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.