SDOI2016 储能表

wjh15101051's space

卧薪尝胆，厚积薄发。

SDOI2016 储能表

Date: Wed May 30 16:05:12 CST 2018

In Category: NoCategory

Description:

求： $\begin{align}\biggl(\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}max(0,i\end{align}$ $xor$ $j-k)\biggr)\%p$

$1\le T\le 5000$ $1\le n,m,k\le 10^{18}$ $1\le p\le 10^9$

Solution:

数位 $DP$ ，转移时有三条边际线，枚举两个方向的值，异或大于等于 $k$ 的边际线的才转移，记录两个值，一个 $cnt$ 表示合法的个数，一个 $sum$ 表示异或和，要把边界线设计在状态里不然 ~~（据说）~~ 会 $T$ 。

Code:


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int testcases;

ll n,m,k,p,dv;

#define MAXL 100

int bitn[MAXL],bitm[MAXL],bitk[MAXL],lenn = 0,lenm = 0,lenk = 0;

int maxn = 0;

bool v[MAXL][2][2][2];

pair<ll,ll> f[MAXL][2][2][2];

pair<ll,ll> dfs(int pos,bool bn,bool bm,bool bk)

{

	if(pos == 0)return make_pair(1ll,0ll);

	if(v[pos][bn][bm][bk])return f[pos][bn][bm][bk];

	pair<ll,ll> res = make_pair(0ll,0ll);

	int limn = (bn ? bitn[pos] : 1),limm = (bm ? bitm[pos] : 1),limk = (bk ? bitk[pos] : 0);

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

	{

		for(int j = 0;j <= limm;++j)

		{

			if((i ^ j) >= limk)

			{

				pair<ll,ll> tr = dfs(pos - 1,bn && (i == limn),bm && (j == limm),bk && ((i ^ j) == limk));

				res.first = (res.first + tr.first) % p;

				res.second = ((res.second + tr.second) % p + ((ll)(i ^ j) * ((1ll << (pos - 1)) % p) * tr.first) % p) % p;

			}

		}

	}

	v[pos][bn][bm][bk] = true;f[pos][bn][bm][bk] = res;

	return res;

}

void work()

{

	memset(v,false,sizeof(v));

	scanf("%lld%lld%lld%lld",&n,&m,&k,&p);--n;--m;dv = k;

	lenn = 0;memset(bitn,0,sizeof(bitn));

	lenm = 0;memset(bitm,0,sizeof(bitm));

	lenk = 0;memset(bitk,0,sizeof(bitk));

	while(n > 0){bitn[++lenn] = n & 1;n = n >> 1;}

	while(m > 0){bitm[++lenm] = m & 1;m = m >> 1;}

	while(k > 0){bitk[++lenk] = k & 1;k = k >> 1;}

	maxn = max(lenk,max(lenn,lenm));

	pair<ll,ll> ans = dfs(maxn,true,true,true);

	cout << (ans.second - (ans.first * (dv % p)) % p + p) % p << endl;

	return;

}

int main()

{

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		work();

	}

	return 0;

}

In tag: DP-数位DP

wjh15101051