[SDOI2016]储能表

一、题目

点此看题

二、解法

不要把这道题从图形的角度考虑,我们考虑它的本质就是求:
i=0n1j=0m1max((i xor j)k,0)\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}\max((i\space xor\space j)-k,0)i=0∑n−1​j=0∑m−1​max((i xor j)−k,0)可以考虑数位dpdpdp,只不过特殊的是我们要同时维护两个数,而且数位指的是二进制位,设f[i][a][b][c]f[i][a][b][c]f[i][a][b][c]为dpdpdp到了二进制的第iii位,是否顶到nnn的上界,是否顶到mmm的上界,是否顶到kkk的上界。

转移就枚举两个数当前位选什么,然后验证a,b,ca,b,ca,b,c,这里还要维护一个个数g[i][a][b][c]g[i][a][b][c]g[i][a][b][c],转移时个数直接累加,答案就加上当前位的贡献在乘上个数,剩下的就是数位dpdpdp日常操作了,贴个代码qwqqwqqwq。

#include <cstdio>
#include <cstring>
#define int long long
int read()
{
    int x=0,flag=1;
    char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*flag;
}
int T,n,m,k,p;
int f[62][2][2][2],g[62][2][2][2];
void init()
{
    n=read();
    m=read();
    k=read();
    p=read();
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    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 && xx>x) || (b && yy>y) || (c && zz<z)) continue;
                                int aa=(a && xx==x),bb=(b && yy==y),cc=(c && zz==z);
                                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]);
}
signed main()
{
    T=read();
    while(T--)
    {
        init();
    }
}

上一篇:[SDOI2016]排列计数


下一篇:洛谷P4069 [SDOI2016]游戏(李超线段树)