「SDOI2016」储能表（数位dp）

神仙数位 \(dp\) 系列 可能我做题做得少 \(QAQ\)

\(f[i][0/1][0/1][0/1]\) 表示第 \(i\) 位 \(n\) 是否到达上界 \(m\) 是否到达上界 \(k\) 是否到达下界。我用一个 \(pair\) 存，\(first\) 记录方案数，\(second\) 记录所有的和。

\(ans=(P.S-k*P.F)\%mod\)

那么我们每次枚举该位为 \(0/1\) 就可以转移了，逐位计算贡献。

\(Code\ Below:\)

#include <bits/stdc++.h>

#define ll long long

#define pll pair<ll,ll>

#define mp make_pair

#define F first

#define S second

using namespace std;

ll n,m,k,mod;pll f[70][2][2][2];

bool vis[70][2][2][2];

pll dfs(int len,bool N,bool M,bool K){

	if(len<0) return mp(1,0);

	if(vis[len][N][M][K]) return f[len][N][M][K];

	vis[len][N][M][K]=1;

	pll ret=mp(0,0),P;

	bool lim_n=N?(n>>len)&1:1,lim_m=M?(m>>len)&1:1,lim_k=K?(k>>len)&1:1;

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

		for(int j=0;j<=lim_m;j++){

			if(K&&(i^j)<lim_k) continue;

			P=dfs(len-1,N&&i==lim_n,M&&j==lim_m,K&&(i^j)==lim_k);

			ret.F=(ret.F+P.F)%mod;

			ret.S=(ret.S+P.S+(i^j)*(1ll<<len)%mod*P.F)%mod;

		}

	return f[len][N][M][K]=ret;

}

inline void solve(){

	memset(f,0,sizeof(f));

	memset(vis,0,sizeof(vis));

	scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);

	n--;m--;

	ll N=n,M=m,K=k;int Max=0,now=0;

	while(N) N>>=1,now++;Max=max(Max,now);now=0;

	while(M) M>>=1,now++;Max=max(Max,now);now=0;

	while(K) K>>=1,now++;Max=max(Max,now);now=0;

	pll P=dfs(Max-1,1,1,1);

	printf("%lld\n",(P.S-k%mod*P.F%mod+mod)%mod);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--) solve();

    return 0;

}