洛谷4067 [SDOI2016]储能表

Luogu

BZOJ

分析

首先拆式子,变成$\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}f(i,j)-k\times\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}[f(i,j)]$

设$f[i][0/1][0/1][0/1]$表示第$i$位,$n$是否到了上界,$m$是否到了上界,$k$是否到了上界。

然后用一个pair来当返回值,两部分同时转移。

血的教训:$long\ long$左移一定要写成$1ll<<x$,如果写成$1<<x$会$\color{red}{\text{WA}}$!

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,m,k,MOD,cnt;
int vis[100][2][2][2];
pii f[100][2][2][2];

inline int len(int x) {
    int qwq=0; while (x) x>>=1,++qwq; return qwq;
}
inline void pls(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

inline pii dfs(int pos,bool fn,bool fm,bool fk) {
    if (!pos) return mp(0,1);
    if (vis[pos][fn][fm][fk]) return f[pos][fn][fm][fk];
    vis[pos][fn][fm][fk]=1;
    pii ans=mp(0,0);
    int ln=(n>>(pos-1))&1,lm=(m>>(pos-1))&1,lk=(k>>(pos-1))&1;
    for (re int i=0;i<=(fn?ln:1);++i)
        for (re int j=0;j<=(fm?lm:1);++j) {
            int k=i^j;
            if (fk&&k<lk) continue;
            pii now=dfs(pos-1,fn&&(i==ln),fm&&(j==lm),fk&&(k==lk));
            pls(ans.first,((1ll<<(pos-1))*k%MOD*now.second+now.first)%MOD); //一定要写1ll
            pls(ans.second,now.second);
        }
    return f[pos][fn][fm][fk]=ans;
}

mainint main() {
    int T=read();
    while (T--) {
        memset(vis,0,sizeof(vis));
        n=read()-1,m=read()-1,k=read(),MOD=read();
        cnt=max(max(len(n),len(m)),len(k));
        pii ans=dfs(cnt,1,1,1);
        printf("%lld\n",(ans.first-k%MOD*ans.second%MOD+MOD)%MOD);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 56 PM

发表评论