【Atcoder】 [ARC144D] AND OR Equation

题目链接

Atcoder方向
Luogu方向

题目解法

考虑满足条件 $2$ 的形式为 $a_n=p_0+\sum _{i\in n}{p}_i$
这是一步很巧妙的转化，神奇地利用了 $\&$ 和 $|$ 的性质，把求 $a$ 的方案数转化为求 $p$ 的方案数
考虑如何满足条件 $1$，令 $p_i<0$ 的和为 $X$，$p_i>0$ 的和为 $Y$，那么 min ⁡ { a i } = X + p 0 , max ⁡ { a i } = Y + p 0 \min\{a_i\}=X+p_0,\;\max\{a_i\}=Y+p_0 min{ai​}=X+p0​,max{ai​}=Y+p0​
所以可以得出 $-X\le p_0\le k-Y$，所以合法的 $p_0$ 取值有 $k-(Y-X)+1$ 种
考虑 $Y-X=\sum |a_i|$，所以 $k-(Y-X)-1=k+1-\sum |p_i|$

考虑枚举 $p$ 中非 $0$ 的个数，正负性有 $2^i$ 种，$s$ 表示绝对值之和，然后就是 $s$ 个球分给 $i$ 个盒子，每个盒子不为空，且要分完的方案数（经典问题），最后再乘上 $p_0$ 的取值方案数
所以 $Ans=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)2^i\sum _{s=i}^{k+1}\left(\genfrac{}{}{0ex}{}{s-1}{i-1}\right)(k+1-s)$
只考虑 $$\begin{gathered} \sum _{s=i}^{k+1}\left(\genfrac{}{}{0ex}{}{s-1}{i-1}\right)(k+1-s) \\ =\sum _{s=i}^{k+1}(k+1)\left(\genfrac{}{}{0ex}{}{s-1}{i-1}\right)-s\left(\genfrac{}{}{0ex}{}{s-1}{i-1}\right) \\ =(k+1)\left(\genfrac{}{}{0ex}{}{k+1}{i}\right)-\sum _{s=i}^{k+1}i\left(\genfrac{}{}{0ex}{}{s}{i}\right) \\ =(k+1)\left(\genfrac{}{}{0ex}{}{k+1}{i}\right)-i\left(\genfrac{}{}{0ex}{}{k+2}{i+1}\right) \end{gathered}$$
展开，然后化简，这里就不细写了
最后化简出来是 $Ans=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)2^i\left(\genfrac{}{}{0ex}{}{k+1}{i+1}\right)$

直接求解即可，时间复杂度 $O(n)$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=300100,P=998244353;
int n,k,fac[N],inv[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
int qmi(int a,int b){int res=1;for(;b;b>>=1){if(b&1) res=res*a%P;a=a*a%P;}return res;
}
int C(int a,int b){ return fac[a]*inv[b]%P*inv[a-b]%P;}
signed main(){n=read(),k=read();fac[0]=1;for(int i=1;i<=n+1;i++) fac[i]=fac[i-1]*i%P;inv[n+1]=qmi(fac[n+1],P-2);for(int i=n;i>=0;i--) inv[i]=inv[i+1]*(i+1)%P;int ans=0,res=(k+1)%P;for(int i=0,pw=1;i<=n;i++,pw=pw*2%P){ans=(ans+C(n,i)*pw%P*res%P*inv[i+1])%P;res=res*((k+1-i-1)%P)%P;}printf("%lld",ans);return 0;
}