ABC317F题解

让人头大的数位DP。建议评蓝。个人认为不适合放ABC的F。

将三个数二进制拆分，使三个数异或为0相当于每个二进制位三个数中有0或2个是1。

所以考虑数位DP，设 \(dp[i][m1][m2][m3][lim1][lim2][lim3]\) 为第 \(i\) 位，三个数模 \(a\) , \(b\) , \(c\) 分别是 \(m1\) , \(m2\) , \(m3\) ，以及三个数有没有最高位限制。

这道题比较特殊。仔细想想可以发现这道题最高位限制必须放状态里。

下文设 \(A[i]\) 为 \(n\) 的第 \(i\) 位。

马上烧脑起来了。

一个状态 \(dp[i][m1][m2][m3][lim1][lim2][lim3]\) 可以如此转移过来：

若 \(A[i]=1\) ：

首先，\(dp[i-1][m1][m2][m3][0][0][0]\) 可以对状态产生贡献，对应三个数的第 \(i\) 位全部为 \(0\) 的情况。

然后继续分类讨论三种情况，这里举例一种。

若 \(lim1=0\) 且 \(lim2=0\) ：

则 \(dp[i-1][(m1+(1<<i))\mod a][(m2+(1<<i))\mod b][m3][lim1\ \And\ !A[i]][lim2][lim3]\) 可以贡献。对应 \(x1\) , \(x2\) 的第 \(i\) 位为1，\(x3\) 的第 \(i\) 位为0的情况。

另外两个情况，同理。

若 \(A[i]=0\) ：

那么就只有 \(dp[i-1][m1][m2][m3][lim1][lim2][lim3]\) 可以对状态产生贡献，还是对应三个数的第 \(i\) 位全部为 \(0\) 的情况，只是三个高位限制不一样了。

最核心的DP转移到这里就完了。还没完，我们又发现我们还要减去三个数中有数为0的情况。

为此还要再跑一次数位DP专门处理。枚举 \(x1\) , \(x2\) , \(x3\) 为0的情况。

举个例子，现在考虑的是 \(x3\) 为0，那么就设 \(dp2[i][m1][m2]\) 为第 \(i\) 位， \(x1\) , \(x2\) 模 \(a\) , \(b\) 为 \(m1\) , \(m2\) 的情况。

这个DP很简单，并没有分类讨论。

\(dp2[i][m1][m2]=dp2[i-1][(m1+(1<<i))\mod a][(m2+(1<<i))\mod b]\)

\(x1\) , \(x2\) 为0还是同理。

像这样跑三次就可以求出三个数中有数为0的不合法贡献。

最后还有一个细节就是这样会把三个数全0的情况算三次，加回去2即可。

code

丑。

//writer:Oier_szc

#include <bits/stdc++.h>
#define TS puts("I AK IOI");
#define int long long
using namespace std;
const int N=2005,mod=998244353;
int n,a,b,c,ans=0;
int dp[70][15][15][15][2][2][2];
int A[70],yes[70],len=-1;
int dfs(int deep,int m1,int m2,int m3,bool lim1,bool lim2,bool lim3)
{
	if(deep==-1) return m1==0&&m2==0&&m3==0;
	if(dp[deep][m1][m2][m3][lim1][lim2][lim3]!=-1) return dp[deep][m1][m2][m3][lim1][lim2][lim3];
	int res=0;
	if(A[deep]) res=(res+dfs(deep-1,m1,m2,m3,0,0,0))%mod;
	else res=(res+dfs(deep-1,m1,m2,m3,lim1,lim2,lim3))%mod;
	if(A[deep]||(!lim2&&!lim3)) res=(res+dfs(deep-1,m1,(m2+(1ll<<deep))%b,(m3+(1ll<<deep))%c,lim1&&!A[deep],lim2,lim3))%mod;
	if(A[deep]||(!lim1&&!lim3)) res=(res+dfs(deep-1,(m1+(1ll<<deep))%a,m2,(m3+(1ll<<deep))%c,lim1,lim2&&!A[deep],lim3))%mod;
	if(A[deep]||(!lim1&&!lim2)) res=(res+dfs(deep-1,(m1+(1ll<<deep))%a,(m2+(1ll<<deep))%b,m3,lim1,lim2,lim3&&!A[deep]))%mod;
	dp[deep][m1][m2][m3][lim1][lim2][lim3]=res;
	return res;
}
int dp2[70][15][15],M1,M2;
int dfs2(int deep,int m1,int m2,int lim)
{
	if(deep==-1) return m1==0&&m2==0;
	if(dp2[deep][m1][m2]!=-1&&!lim) return dp2[deep][m1][m2];
	int up=lim?A[deep]:1ll,res=0;
	for(int i=0;i<=up;++i)
	{
		res+=dfs2(deep-1,(m1+(i<<deep))%M1,(m2+(i<<deep))%M2,lim&&i==up);
	}
	if(!lim) dp2[deep][m1][m2]=res;
	return res;
}
signed main()
{
	scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
	while(n)
	{
		A[++len]=n%2;
		n/=2;
	}
	int cnt_0=-2;
	M1=a,M2=b;
	memset(dp2,-1,sizeof(dp2));
	cnt_0=(cnt_0+dfs2(len,0,0,1))%mod;
	M1=a,M2=c;
	memset(dp2,-1,sizeof(dp2));
	cnt_0=(cnt_0+dfs2(len,0,0,1))%mod;
	M1=b,M2=c;
	memset(dp2,-1,sizeof(dp2));
	cnt_0=(cnt_0+dfs2(len,0,0,1))%mod;
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",(dfs(len,0,0,0,1,1,1)-cnt_0+mod)%mod);
	return 0;
}