题解 P4067 【[SDOI2016]储能表】

· · 题解

修改了一下，update了一种新做法

来我们接触到这篇题目，我们仔细考虑一下是数位dp。

可以发现可以一位一位的处理，每一位可以从前一位推出，所以可以考虑数位dp。

    我们把要统计的数变为二进制表示，先考虑n位二进制的数，再考虑n-1位的数。f[i][1/0][1/0][1/0]为已经考虑到了第i位，第i位是否比n（第i位）小，第i位是否比m小， 是否比k小的总共分数。

    g[i][1/0][1/0][1/0]为已经考虑到了第i位，第i位是否比n（第i位）小，第i位是否比m小，是否比k小的所有情况总数。

    我们从大到小考虑每一位，我们就可以推出一个式子g[i][aa][bb][cc] += g[i+1][a][b][c];

    如果从状态(i,a,b,c)可以转移到状态(i-1, aa, bb, cc);

f[i][aa][bb][cc] += f[i+1][a][b][c] + (zz-z)(1<<i)g[i+1][a][b][c];

    前一项不必多说，后一项就是对于每一种可能都可以在前面加上1/0。
    最然数据范围是10 18，但是log2(10^18) = 60。所以我们循环60次即可。

代码如下

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
ll f[62][2][2][2], g[62][2][2][2];
ll n, m, k, T, p;
int main()
{
    scanf("%lld", &T);
    while (T--) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    scanf("%lld %lld %lld %lld", &n, &m, &k, &p);
    g[61][1][1][1] = 1;
    for (int i = 60; i >= 0; i--) {
    int x = (n >> i) & 1, y = (m >> i) & 1, z = (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 (f[i + 1][a][b][c] || g[i + 1][a][b] [c]) {
                        for (int xx = 0; xx < 2; xx++) {
                            for (int yy = 0; yy < 2; yy++) {
                                int zz = xx ^ yy;
                                if ((a && x < xx) || (b && y < yy) || (c && z > zz))
                                    continue;
                                int aa = (a && x == xx), bb = (b & y == yy),cc = (c && z == zz);
                                g[i][aa][bb][cc] = (g[i][aa][bb][cc] + g[i + 1][a][b][c]) % p;
                                f[i][aa][bb][cc] = (f[i][aa][bb][cc] + f[i + 1][a][b][c] + ((zz - z) + p) % p * ((1ll << i) % p) % p * g[i + 1][a][b][c] % p) % p;
                                }
                            }
                        }    
                    }
                }
            }
        }
        printf("%lld\n", f[0][0][0][0]);
    }
}

分割线---------------------------------------------------------------

这个题可以暴力打表。

初拿此题还是一年前，当时写的数位dp，现在看来可以打表玩。

我们看一下要求的式子：

\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}\max((i xor j)-k,0)

然后我们定义一个sum函数，该函数如下：

sum(x,y):$求$\sum_{now=x}^ynow

其实就是想拆个西格玛下来。。。。算是化简吧。。。。。

然后我们在定义一个calc函数。。。美其名曰求题目及若干子问题（好吧我承认就是递归求解）

calc(n,m,k)

那么问题来了，这两个函数是怎么来的？

首先我们需要打个表！！！！！

然后我们发现这个表好像是对称的！！！！

这个叫啥对称？？对角对称？？中心对称再拧回来？？？总之是对称的就是了。

然后对于\forall p=2^i，p*p的左上角的是(0,0)的正方形，它的每一行，每一列的和是固定的。且它下面的和右面的同等大小的正方形恰好是在它的基础上加一个2^i，它的右下角的正方形是与它完全一样的。

Like this：

然后就可以递归求解了

这里说一下calc的写法。

我们先求出比n,m中较大的数小的最大的2的次幂然后减一，这个次幂设为t的话（下面假设n大一点），那么我们得到了一个t*t的正方形。

如果这个正方形在n*m的矩形里面，那我们就可以递归它的下面一部分，右边一部分，和右下角一部分。

如果这个矩形已经超过了n,m的矩形的范围，我们可以直接计算出t,m这个矩形的数值（t行—列的和是固定的，因为t是2的次幂），接着再递归求解(n-i)*m这个矩形内的数值。

然后我们就可以写个大模拟。。。。。。

然后就可了。

事实证明，什么dp都是浮云，打表暴力才是王道！！！（划死

上代码

#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#define LL long long
#define inf 1000000009
using namespace std;
inline LL read() {
    LL s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
LL T,N,M,K,p,tmp;
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 calc(LL n,LL m,LL k) {
    if(n < 0||m < 0) {
        return 0;
    }
    if(n == 0 && m == 0) {
        return max(((N - 1) ^ (M - 1)) - K,tmp) % p;
    }
    if(n < m) {
        swap(n,m);
    }
    LL l = 0,t;
    while((1LL << l) <= n + 1) l++;
    l--;
    t = (1LL << l) - 1;
    if(t <= m) {
        return ((t + 1) % p * sum(-k,t - k) % p + (n - t + m - t) % p * sum(t + 1 - k,t + t + 1 - k) % p + calc(n - t - 1,m - t - 1,k)) % p;
    } else {
        return ((m + 1) % p * sum(max(-k,tmp),max(tmp,t - k)) % p + calc(n - t - 1,m,k - t - 1)) % p;
    }
}
void init() {
    N = read(),M = read(),K = read(),p = read();
    LL now = calc(N - 1,M - 1,K);
    printf("%lld\n",now);
    return ;
}
void solve() {
    T = read();
    while(T--){
        init();
    }
    return ;
}
int main(){
    solve();
    return 0;
}