F - AND/OR Editorial by evima
First, let us consider the following problem. It is easier than fully solving this problem.
If operation \(2\) can be performed at most \(K\) times in total, what is \(M\)?
How should we solve this?
In fact, it is optimal to make the last \(K\) operations operation \(2\).
This is because, since \((a\ {\rm AND}\ b)\ {\rm OR}\ c\) is always at least \(c\), and \((a\ {\rm OR}\ b)\ {\rm AND}\ c\) is always at most \(c\), for an operation sequence in which an \({\rm AND}\) immediately follows an \({\rm OR}\), swapping them does not decrease the final value of \(x\).
Henceforth, we assume \(M\) is known.
Let us consider tracing back through the operations from the end, maintaining the following information.
- Fixed flag \(f\)
- The \(k\)-th bit of \(f\) is \(1\) if and only if it has been determined that the \(k\)-th bit of the final \(x\) coincides with the \(k\)-th bit of \(M\).
For digits where the fixed flag is not set, we can decide the type of operation working backwards as follows.
- For a digit that is \(0\) in \(M\):
- When that digit is \(0\) in the currently considered \(A_i\) … (a)
- Taking \({\rm AND}\) sets the fixed flag, and taking \({\rm OR}\) leaves the fixed flag unset.
- When that digit is \(1\) in the currently considered \(A_i\) … (b)
- Taking \({\rm AND}\) leaves the fixed flag unset, and taking \({\rm OR}\) is not allowed.
- When that digit is \(0\) in the currently considered \(A_i\) … (a)
- For a digit that is \(1\) in \(M\):
- When that digit is \(0\) in the currently considered \(A_i\) … (c)
- Taking \({\rm AND}\) is not allowed, and taking \({\rm OR}\) leaves the fixed flag unset.
- When that digit is \(1\) in the currently considered \(A_i\) … (d)
- Taking \({\rm AND}\) leaves the fixed flag unset, and taking \({\rm OR}\) sets the fixed flag.
- When that digit is \(0\) in the currently considered \(A_i\) … (c)
Let us consider a DP-like approach with this fixed flag as the key.
The fixed flag can take \(O(\max A_i)\) possible values, which under this problem’s constraints is \(2^{60}\), so implementing this approach naively is insufficient in both time and space complexity.
Does this approach really not lead to a correct solution?
Let \(o\) be the \({\rm OR}\) of all elements of \(A\). We decide that if all digits that are \(1\) in \(o\) have become fixed (that is, the case where a digit could become \(1\), but the value of \(x\) can no longer be changed there), then such a state is immediately discarded. … ★
Then, it can be proved that at each stage of tracing back through the operations, there are at most two possible fixed flags, or in other words, at most two possible suffixes of the operation sequence.
Initially, the fixed flag is \(0\).
While tracing back, whenever one of the two operations is forbidden due to (b) or (c), the operation does not branch.
The first time the fixed flag branches, only (a) and (d) can have occurred.
At that point, all digits for which the fixed flag remains unset agree between \(A_i\) and \(M\), and the state branches into the following two cases.
- Only digits that are \(0\) in \(M\) remain with the fixed flag unset.
- From here on, only (a) and (b) can occur, and when (b) occurs, no branching occurs. When only (a) occurs and branching occurs, one branch is always in a state where the value of \(x\) can no longer be changed, so by our rule, we may regard this as not branching at all.
- Only digits that are \(1\) in \(M\) remain with the fixed flag unset.
- This can be shown by an analogous argument.
From the above, we now see a way to solve this problem in \(O(N)\) by tracing back through the operation sequence from the end while maintaining the fixed flag \(f\).
Let us consider tracing back while maintaining, as a single state, \((\) the fixed flag, the number of remaining operation \(2\)’s, the number of ways corresponding to the situation of the left two values \()\). The initial state is \((0,K,1)\).
We trace this back in a manner similar to DFS or BFS.
Then, when the fixed flag reaches a state matching the rule ★, the number of ways to decide the remaining operations is expressed as the following sum of binomial coefficients.
- \(\displaystyle \sum_{i=0}^{a} \binom{b}{i}\)
- where \(a\) is the number of remaining operation \(2\)’s, and \(b\) is the number of remaining operations overall.
This allows us to solve this problem in \(O(N^2)\) time.
However, \(O(N^2)\) is still not sufficient. What should we do?
We can set the initial value of the third element of the state not to \(1\) but to \(\displaystyle \sum_{i=0}^{K} \binom{N}{i}\), and maintain the desired sum while tracing back. This way, we can obtain the desired sum of binomial coefficients in \(O(1)\), allowing us to solve this problem in \(O(N)\) time.
It may help to picture Pascal’s triangle when setting up the detailed transition formulas.
We maintain the sum of several elements from the left in a certain row of Pascal’s triangle, and ascend to the row above while maintaining this state.
The operation required during the transition decreases \(N\) by \(1\), and decreases \(K\) by \(0\) or \(1\).
Let us actually try to quickly compute \(\displaystyle \sum_{i=0}^{K} \binom{N-1}{i}\) from \(\displaystyle \sum_{i=0}^{K} \binom{N}{i}\).
Let \(\displaystyle S_u=\sum_{i=0}^{K} \binom{N-1}{i}, S_d=\sum_{i=0}^{K} \binom{N}{i}\).
Observing Pascal’s triangle, each element added in \(S_u\) is generally added twice in \(S_d\).
However, \(\displaystyle \binom{N-1}{K}\) alone is added to \(S_d\) only once.
From the above, the formula \(\displaystyle S_d = 2S_u - \displaystyle \binom{N-1}{K}\) holds, so we can find \(S_u\) from \(S_d\) in \(O(1)\) time.
Similarly, we can also trace back in the case where \(K\) decreases by \(1\) in \(O(1)\) time.
Eventually, this problem can be solved in \(O(N \log{(\max A_i)})\) overall (if we treat bitwise operations as taking constant time and use it, the problem can be solved in \(O(N)\) time under the problem’s constraints).
Note that even if the fixed flag is not completely set by the time we trace back to the first operation, we still achieve \(x=M\) as long as all digits that are \(1\) in \(M\) are fixed.
Sample Implementation (C++):
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const ll MXM=200005;
using mint = modint998244353;
vector<mint> fac(MXM),invfac(MXM);
void calc_fac(){
fac[0]=mint(1);
for(ll i=1;i<MXM;i++){
fac[i]=fac[i-1]*mint(i);
}
invfac[MXM-1]=mint(1)/fac[MXM-1];
for(ll i=MXM-2;i>=0;i--){
invfac[i]=invfac[i+1]*mint(i+1);
}
}
mint nCr(ll n,ll r){
if(n<r){return 0;}
return fac[n]*invfac[r]*invfac[n-r];
}
using tup=tuple<ll,ll,mint>;
int main(){
ll al=(1ll<<60)-1;
calc_fac();
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
ll n,k;
cin >> n >> k;
ll o=0;
vector<ll> a(n);
for(auto &nx : a){
cin >> nx;
o|=nx;
}
ll d1=0;
for(ll i=n-k;i<n;i++){d1|=a[i];}
ll d0=(al^d1);
mint ini(0);
for(ll i=0;i<=k;i++){ ini+=nCr(n,i); }
vector<tup> sta={{0,k,ini}};
mint res=0;
for(ll i=n-1;i>=0;i--){
{
vector<tup> nsta;
for(auto [f,rk,pat] : sta){
ll e0=((al^f)&d0);
ll e1=((al^f)&d1);
int ban=0;
if((e0&a[i])>0){ban|=2;}
if((e1&(al^a[i]))>0){ban|=1;}
if((ban&1)==0){
// and
mint npat=(pat+nCr(i,rk))/mint(2);
nsta.push_back(tup{(f|(e0&(al^a[i]))),rk,npat});
}
if((ban&2)==0 && rk>0){
// or
mint npat=(pat-nCr(i,rk))/mint(2);
nsta.push_back(tup{(f|(e1&a[i])),rk-1,npat});
}
}
sta=nsta;
}
{
vector<tup> nsta;
for(auto [f,rk,pat] : sta){
if((f&o)==o){
res+=pat;
}
else{
nsta.push_back(tup{f,rk,pat});
}
}
sta=nsta;
}
}
for(auto [f,rk,pat] : sta){
if((f&d1)==d1){res+=pat;}
}
cout << res.val() << "\n";
}
return 0;
}
posted:
last update: