Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4067 [SDOI2016]储能表

Posted on Edited on In
Symbols count in article: 2.9k Reading time ≈ 3 mins.

这就是我和巨佬的差距

储能表

题意

$T \le 5000$ 组数据，每次给定 $n, m, k \le 10^{18}$ ，求：
$$
\sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} \max((i \oplus j) - k, 0)
$$
答案对 $p \le 10^9$ 取模

蒻蒟的挣扎

一看见 $5000, 10^{18}$ 吓了一跳，后来发现是数位 dp

首先原式里面一个 $\max$ 很不有好（因为它是为了保证非负），不妨考虑只管异或值大于 $k$ 的数对 $(i, j)$ ，就不用管 $\max$ 了，更具体的，我们求出“异或值大于 $k$ 的数对的个数 $A$ ”和“所以异或值大于 $k$ 的数对的异或值之和 $B$ ”，那么 $Ans = B - A * k$

考虑分别求 $A, B$ ，定义 d[0/1][i][0/1][0/1][0/1] ，让 $d[0]$ 表示“从高到低到了二进制的第 $i$ 位，已经考虑的位数是/否到达 $n$ 的上界，是/否到达 $m$ 的上界，是/否到达 $k$ 的下界，此时的合法个数”， $d[1]$ 类似，但表示的是“异或值之和”

实现用记忆化搜索，慢一点点但好打的多

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 70;
LL n, m, k;
int d[2][N][2][2][2], p, mxl;
bool vis[N][2][2][2];
void dp(int len, int fn, int fm, int fk, int &as0, int &as1)
{
    int &f = d[0][len][fn][fm][fk], &g = d[1][len][fn][fm][fk];
    if (len > mxl) return as0 = 1, as1 = 0, void();
    if (vis[len][fn][fm][fk]) return as0 = f, as1 = g, void();
    vis[len][fn][fm][fk] = true;
    int pn = (n >> mxl - len) & 1, pm = (m >> mxl - len) & 1, pk = (k >> mxl - len) & 1;
    for (int i = 0; i <= (fn ? pn : 1); ++i)
        for (int j = 0, pf, pg; j <= (fm ? pm : 1); ++j) if (!fk || (i ^ j) >= pk)
        {
            dp(len + 1, fn && (i == pn), fm && (j == pm), fk && ((i ^ j) == pk), pf, pg);
            f = (f + pf) % p, g = ((LL)g + (1ll << mxl - len) * (i ^ j) % p * pf + pg) % p;
        }
    as0 = f, as1 = g;
}
int main()
{
    int T, ct, ans[2];
    LL t;
    for (scanf("%d", &T); T--; memset(vis, false, sizeof vis), memset(d, 0, sizeof d), mxl = 0)
    {
        scanf("%lld %lld %lld %d", &n, &m, &k, &p), --n, --m;
        for (ct = 0, t = n; t; ++ct, t >>= 1);mxl = max(mxl, ct);
        for (ct = 0, t = m; t; ++ct, t >>= 1);mxl = max(mxl, ct);
        for (ct = 0, t = k; t; ++ct, t >>= 1);mxl = max(mxl, ct);
        dp(1, 1, 1, 1, ans[0], ans[1]);
        printf("%d\n", ((LL)ans[1] - k % p * ans[0] % p + p) % p); //这里太坑了,k是LL,一定要先模一下
    }
    return 0;
}

巨佬的 show time

有巨佬用打表 + 模拟过了……

思路和这位差不多

巨佬的代码

懒得打了，直接贴同机房巨佬的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int T;

ll n, m, k, p, tmp;

template <class T>
void read(T &x)
{
	char ch;
	bool flag = false;
	while((ch = getchar()) < '0' || ch > '9')
		if (ch == '-') flag = true;
	x = ch - '0';
	while('0' <= (ch = getchar()) && ch <= '9') x = x * 10 + (ch - '0');
	if (flag) x = -x;
}

ll sum(ll x, ll y)
{
	if (x < 0) x = 0;
	if (y < 0) y = 0;
	ll res = y - x + 1;
	if (res & 1) return (res % p) * ((x + y >> 1) % p) % p;
	else return ((res + 1 >> 1) % p) * ((x + y) % p) % p;
}

ll getans(ll x, ll y, ll z)
{
	if (x < 0 || y < 0) return 0;
	if (x == 0 && y == 0) return max(((n - 1) ^ (m - 1)) - k, tmp) % p;
	if (x < y) swap(x, y);
	ll l =0, t;
	while((1ll << l) <= x + 1) l++;
	l--;
	t = (1ll << l) - 1;
	if (t <= y) return ((t + 1) % p * sum(-z, t - z) % p + (x - t + y - t) % p * sum(t + 1 - z, t * 2 + 1 - z) % p + getans(x - t - 1, y - t - 1, z)) % p;
	else return ((y + 1) % p * sum(max(-z, tmp), max(tmp, t - z)) % p + getans(x - t - 1, y, z - t - 1)) % p;
}

int main()
{
	read(T);
	while(T--)
	{
		read(n), read(m), read(k), read(p);
		printf("%lld\n", getans(n - 1, m - 1, k));
	}
}