【BZOJ 4513】[SDOI2016] 储能表

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4513

先来%一波Menci的强行找规律(:з」∠)：https://dn-menci.qbox.me/sdoi2016-table/
然后就是std用的数位DP：http://www.ruiker1997.tk/bzoj-4513

一直感觉这个题目的数位DP很牵强
于是一直尝试使用以前的数位DP的写法来写
然后发现，嘴巴ac还是挺容易的，但真要写出来，还真心不好写
于是代码就算了吧。

—– UPD 2016.9.29 —–
还是补一份代码吧
以前数位DP都不是这么写的
不过感觉这么写，如果没有多组询问还是挺清真的

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k; 

int main(){
	int T; cin>>T; while (T--) {
		cin>>n>>m>>k>>MOD;
		memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
		g[61][0][0][0] = 1;
		for (int i=60;~i;i--) {
			int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
			for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
				for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
					if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
					wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
					(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
					(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
				}
			}
		}	
		cout<<f[0][1][1][1]<<endl;
	}
	return 0;
}