526互联

[ARC144D] AND OR Equation

发布时间 2023-04-29 12:18:32作者: 灰鲭鲨

Problem Statement

You are given positive integers $N$ and $K$. Find the number, modulo $998244353$, of integer sequences $\bigl(f(0), f(1), \ldots, f(2^N-1)\bigr)$ that satisfy all of the following conditions:

  • $0\leq f(x)\leq K$ for all non-negative integers $x$ ($0\leq x \leq 2^N-1$).
  • $f(x) + f(y) = f(x \,\mathrm{AND}\, y) + f(x \,\mathrm{OR}\, y)$ for all non-negative integers $x$ and $y$ ($0\leq x, y \leq 2^N-1$)

Here, $\mathrm{AND}$ and $\mathrm{OR}$ denote the bitwise AND and OR, respectively.

Constraints

  • $1\leq N\leq 3\times 10^5$
  • $1\leq K\leq 10^{18}$

Input

Input is given from Standard Input in the following format:

$N$ $K$

Output

Print the number, modulo $998244353$, of integer sequences that satisfy the conditions.

Sample Input 1

2 1

Sample Output 1

6

The following six integer sequences satisfy the conditions:

  • $(0,0,0,0)$
  • $(0,1,0,1)$
  • $(0,0,1,1)$
  • $(1,0,1,0)$
  • $(1,1,0,0)$
  • $(1,1,1,1)$

Sample Input 2

2 2

Sample Output 2

19

Sample Input 3

100 123456789123456789

二进制的题，考虑拆位处理。

那么会发现，当我们确定了 \(f(0),f(1)\cdots f(2^n)\) 时，整个函数就确定了

具体写出来，就是 \(f(2^{p_1}+2^{p_2}+\cdots+2^{p_m})=(\sum\limits_{i=1}^mf(2^{p_i})-f(0))+f(0)\)

这个式子可以直接打表推出来

那么此时我们知道了所有 \(f(2^p_i)-f(0)\) 的值，我们能否知道有多少个合法的 \(f(0)\)？

注意有 \(f(x)\) 的限制，所以要满足任意的数，\(0\le (\sum\limits_{i=1}^m(f(2^{p_i})-f(0)))+f(0)\le K\)

上面这个式子的最大值和最小值一定是所有正数的和(设为 \(s1\))和所有负数的和(设为s2)，那么

\[s2+f(0)\ge 0,s1+f(0)\le k,-s2\le f(0)\le K-s1 \]

共有 \(K-s1+s2+1\) 种选法

注意到 \(s1-s2=\sum\limits_{i=0}^n|f(2^i)|\)

我们可以往这个方向去列式子。枚举最后的绝对值之和。

\[\sum\limits_{i=n}^{K+1}(K-i+1)C_{i-1}^{n-1} \]

\[=(K+1)\sum\limits_{i=n}^{K+1}C_{i-1}^{n-1}-\sum\limits_{i=n}^{K+1}iC_{i-1}^{n-1} \]

\[=(K+1)\sum\limits_{i=n}^{K+1}C_{i-1}^{n-1}-n\sum\limits_{i=n}^{K+1}C_i^n(融入公式) \]

\[=(K+1)C_{K+1}^n-nC_{K+2}^{n+1}(上指标求和) \]

\[=C_{K+1}^{n+1}(通分可得，不写了) \]

此时我们还要给每个数分配正负，发现0我们无法分配。枚举有多少个非0点，然后给答案加上 \(C_{K+1}^{i+1}\times 2^i\times C_n^i\)

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,P=998244353;
int n,f[N],iv[N],inv[N],c[N],ans;
long long k;
int C(int x,int y)
{
	return 1LL*f[x]*iv[y]%P*iv[x-y]%P;
}
int main()
{
	scanf("%d%lld",&n,&k);
	c[f[0]=f[1]=iv[0]=iv[1]=inv[1]=c[0]=1]=(k+1)%P;
	for(int i=2;i<N;i++)
	{
		f[i]=1LL*f[i-1]*i%P;
		inv[i]=(P-P/i)*1LL*inv[P%i]%P;
		iv[i]=1LL*iv[i-1]*inv[i]%P;
		c[i]=c[i-1]*((k-i+2)%P)%P*inv[i]%P;
	}
	for(int i=0,pw=1;i<=n;i++,(pw<<=1)%=P)
		(ans+=1LL*pw*C(n,i)%P*c[i+1]%P)%=P;
//		printf("%d %d %d\n",i,pw,c[i+1]);
	printf("%d",ans);
}