【Atcoder】 [ARC144D] AND OR Equation
题目链接
Atcoder方向
Luogu方向
题目解法
考虑满足条件 2 2 2 的形式为 a n = p 0 + ∑ i ∈ n p i a_n=p_0+\sum\limits_{i\in n}p_i an=p0+i∈n∑pi
这是一步很巧妙的转化，神奇地利用了 & \& & 和 ∣ | ∣ 的性质，把求 a a a 的方案数转化为求 p p p 的方案数
考虑如何满足条件 1 1 1，令 p i < 0 p_i<0 pi<0 的和为 X X X， p i > 0 p_i>0 pi>0 的和为 Y Y 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 ≤ p 0 ≤ k − Y -X\le p_0\le k-Y −X≤p0≤k−Y，所以合法的 p 0 p_0 p0 取值有 k − ( Y − X ) + 1 k-(Y-X)+1 k−(Y−X)+1 种
考虑 Y − X = ∑ ∣ a i ∣ Y-X=\sum |a_i| Y−X=∑∣ai∣，所以 k − ( Y − X ) − 1 = k + 1 − ∑ ∣ p i ∣ k-(Y-X)-1=k+1-\sum{|p_i|} k−(Y−X)−1=k+1−∑∣pi∣
考虑枚举 p p p 中非 0 0 0 的个数，正负性有 2 i 2^i 2i 种， s s s 表示绝对值之和，然后就是 s s s 个球分给 i i i 个盒子，每个盒子不为空，且要分完的方案数（经典问题），最后再乘上 p 0 p_0 p0 的取值方案数
所以 A n s = ∑ i = 0 n ( n i ) 2 i ∑ s = i k + 1 ( s − 1 i − 1 ) ( k + 1 − s ) Ans=\sum\limits_{i=0}^{n}\binom{n}{i}2^i\sum\limits_{s=i}^{k+1}\binom{s-1}{i-1}(k+1-s) Ans=i=0∑n(in)2is=i∑k+1(i−1s−1)(k+1−s)
只考虑 ∑ s = i k + 1 ( s − 1 i − 1 ) ( k + 1 − s ) = ∑ s = i k + 1 ( k + 1 ) ( s − 1 i − 1 ) − s ( s − 1 i − 1 ) = ( k + 1 ) ( k + 1 i ) − ∑ s = i k + 1 i ( s i ) = ( k + 1 ) ( k + 1 i ) − i ( k + 2 i + 1 ) \sum\limits_{s=i}^{k+1}\binom{s-1}{i-1}(k+1-s)\\=\sum\limits_{s=i}^{k+1}(k+1)\binom{s-1}{i-1}-s\binom{s-1}{i-1} \\=(k+1)\binom{k+1}{i}-\sum\limits_{s=i}^{k+1}i\binom{s}{i} \\=(k+1)\binom{k+1}{i}-i\binom{k+2}{i+1} s=i∑k+1(i−1s−1)(k+1−s)=s=i∑k+1(k+1)(i−1s−1)−s(i−1s−1)=(k+1)(ik+1)−s=i∑k+1i(is)=(k+1)(ik+1)−i(i+1k+2)
展开，然后化简，这里就不细写了
最后化简出来是 A n s = ∑ i = 0 n ( n i ) 2 i ( k + 1 i + 1 ) Ans=\sum\limits_{i=0}^{n}\binom{n}{i}2^i\binom{k+1}{i+1} Ans=i=0∑n(in)2i(i+1k+1)
直接求解即可，时间复杂度 O ( n ) O(n) 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;
}