 # INVXOR - Editorial

Author: Shahjalal Shohag
Tester: Suchan Park
Editorialist: William Lin

Medium-Hard

# PREREQUISITES:

Combinatorics, Discrete Logarithm

# PROBLEM:

The value of a set is the XOR sum of all elements in the set. The beauty of a sequence is defined as the sum of the values of all subsets. Let F(N, B) be the number of non-negative integer sequences of length N with beauty B. Find the smallest B such that F(N, B) \mod M = X or determine that none exist.

# QUICK EXPLANATION:

Let p be the number of distinct bits (powers of 2) which appear in at least one element of the sequence. If we fix the p bits which appear in the sequence, there is only one possible beauty for the sequence, and there are \left ( 2^N-1 \right )^p such sequences (this value \mod M should be X). The minimum beauty is 2^{N-1}\cdot \left( 2^p - 1 \right) and it occurs when we choose the first p bits (2^0, 2^1, \dots, 2^{p-1}). Finding the minimum value of p is a discrete logarithm problem.

# EXPLANATION:

Let a_1, a_2, \dots, a_p be distinct bits which appear in at least one element of a sequence A.

Observation 1. The beauty of A is 2^{N-1} \left ( 2^{a_1}+2^{a_2}+\dots+2^{a_p} \right ).

Proof

Like in most other problems involving bitwise operations, we should consider each bit by itself. Let’s calculate the contribution of bit a_i to the answer.

The xor sum will only contain bit a_i if it appears an odd number of times. Thus, the contribution of bit a_i is x2^{a_i}, where x is the number of subsets of A which contain bit a_i an odd number of times. The value of x is well-known to be 2^{N-1}.

Proof

Consider the sequence B of length N-1 which contains all elements of A except for an element with bit a_i, say x. There are 2^{N-1} ways to choose a subset from B. If that subset has bit a_i an odd number of times, then we cannot add x to the subset. If that subset has bit a_i an even number of times, we must add x to the subset. Thus, each subset of B corresponds to a subset of A with an odd number of occurrences.

We add the contribution for all bits to get 2^{N-1} \left ( 2^{a_1}+2^{a_2}+\dots+2^{a_p} \right ).

Observation 2. There are \left (2^N -1 \right )^p sequences with beauty 2^{N-1} \left ( 2^{a_1}+2^{a_2}+\dots+2^{a_p} \right ).

Proof

Note that given the value of 2^{N-1} \left ( 2^{a_1}+2^{a_2}+\dots+2^{a_p} \right ), we can uniquely determine the distinct bits a_1, a_2, \dots, a_p from the binary representation.

Consider bit a_1. We can choose any subset of the sequence to include bit a_1, except for the empty subset, since bit a_1 needs to appear at least once. There are 2^N-1 such subsets.

Since we have p bits, the total number of ways is \left (2^N -1 \right )^p.

The number of sequences only depend on the value of p. Thus, we should always choose the smallest p bits to calculate the beauty (since we want the minimum). The minimum beauty is for a certain p is 2^{N-1} \left ( 2^0+2^1+\dots+2^{p-1} \right )=2^{N-1}\left ( 2^p-1 \right ).

A smaller value of p gives a smaller beauty, so we should find the minimum value of p such that \left (2^N -1 \right )^p \equiv X \pmod M. This problem is known as discrete logarithm and can be solved in O(\sqrt M) with baby-step giant-step. After we find p, we just need to calculate the minimum beauty and output it.

Note on calculating 2^N \mod M for N given as a string with a lot of digits:

Explanation

2^{1234} \mod M = (2^{123} \mod M)^{10} \mod M * 2^4 \mod M, so we can calculate 2^z \mod M for each prefix z of N without using any big integer classes.

There are also a few edge cases to take care of!

# HIDDEN TRAPS:

• If M=1, B=0.
• If X=0, we don’t need a valid B (in other words, B=1 unless N=1).

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )

const int N = 3e5 + 9;
const int mod = 998244353;

int qpow(int a, int b, int m)
{
int ans = 1 % m;
while(b){
if(b & 1LL) ans = 1LL * ans * a % m;
a = 1LL * a * a % m;
b >>= 1;
}
return ans;
}
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
int operator()(int x) const { return x ^ RANDOM; }
};
//baby step - giant step
//find minimum integer x such that a^x = b (mod m)
//where a and m are co-prime
const int inf = 2e9;
unordered_map<int, int, chash> vals;
int DiscreteLog(int a, int b, int m)
{
int n = (int) sqrt (m + .0) + 1;
int an = 1;
for (int i = 0; i < n; ++i) an = (1LL * an * a) % m;
vals.clear();
for (int p = 1, cur = an; p <= n; ++p)
{
if (!vals[cur]) vals[cur] = p;
cur = (1LL*cur * an) % m;
}
int res = inf;
for (int q = 0, cur = b; q <= n; ++q)
{
if (vals.find(cur) != vals.end())
{
ll ans = 1LL * vals[cur] * n - q;
if(ans < res) res = ans;
}
cur = (1LL * cur * a) % m;
}
if(res == inf) res = -1;
return res;
}
pair<ll, ll> ext_euclid(int a, int b)   // returns x, y | ax + by = gcd(a,b)
{
if(b == 0) return pair<ll, ll>(a >= 0? 1LL : -1LL, 0LL);
else{
pair<ll, ll> d = ext_euclid(b, a % b);
return pair<ll, ll>(d.second, d.first - d.second * (a / b));
}
}
int inverse(int a, int n)  //a and n is coprime
{
pair<ll, ll> ret = ext_euclid(a, n);
return ((ret.first % n) + n) % n;
}
int brute(int a, int b, int m)
{
int nw = 1 % m;
if(nw == b) return 0;
for(int i = 1; i < m; i++){
nw = 1LL * nw * a % m;
if(nw == b) return i;
}
return -1;
}
//Discrete Log but a and m may not be co-prime
int DLOG(int a, int b, int m)
{
if(m == 1) return 0;
if(b == 1) return 0;
if(__gcd(a, m) == 1) return DiscreteLog(a, b, m);
int g = __gcd(a, m);
if(b % g != 0)  return -1;
int p = inverse(a/g, m/g);
int nw = DLOG(a , 1LL * b / g * p % (m/g), m/g);
if(nw == -1) return -1;
return nw + 1;
}
string mx = "1" + string(10000, '0');
int pw;
int32_t main()
{
ios_base::sync_with_stdio(0);
int invof2 = qpow(2, mod - 2, mod);
pw = 1;
for(int i = 1; i < 10; i++) pw[i] = pw[i - 1] * 2;
int t; cin >> t;
assert( 1 <= t && t <= 100);
vals.reserve(1 << 15);
while(t--){
string s; cin >> s;
assert(s != '0');
assert(((int)s.size() < (int)mx.size() || ((int)s.size() == (int)mx.size() && s <= mx)));
int x, m; cin >> x >> m;
assert(x < m && x >= 0 && m >= 1 && m <= 1000000000);
if(m == 1){
cout << 0 << nl;
continue;
}
if((int)s.size() == 1 && s == '1'){
if(x == 1) cout << 0 << nl;
else cout << -1 << nl;
continue;
}
if(x == 0){
cout << 1 << nl;
continue;
}
int base = 1 % m, pwof2 = 1 % mod;
for(auto &c: s){
base = qpow(base, 10, m);
base = 1LL * base * pw[c - '0'] % m;
pwof2 = qpow(pwof2, 10, mod);
pwof2 = 1LL * pwof2 * pw[c - '0'] % mod;
}
base = (base - 1 + m) % m;
int on = DLOG(base, x, m);
if(on == -1) cout << -1 << nl;
else{
int ans = (qpow(2, on, mod) - 1 + mod) % mod;
int tmp = 1LL * pwof2 * invof2 % mod;
ans = 1LL * ans * tmp % mod;
cout << ans << nl;
}
}
return 0;
}

Tester's Solution
//
// Created by ë°�ì��ì°¬ on 2020/02/22.
//

#include <bits/stdc++.h>

const int BUFFER_SIZE = int(1.1e5);

char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;

char seekChar() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
assert(_buf_pos < _buf_len);
return _buf[_buf_pos];
}

bool seekEof() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
return _buf_pos >= _buf_len;
}

char ret = seekChar();
_buf_pos++;
return ret;
}

int readInt(int lb, int rb) {
int mul = 1;
if(c == '-') {
mul = -1;
}
assert(isdigit(c));

long long ret = c - '0';
char first_digit = c;
int len = 0;
while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
ret = ret * 10 + readChar() - '0';
}
ret *= mul;

if(len >= 2) assert(first_digit != '0');
assert(len <= 18);
assert(lb <= ret && ret <= rb);
return (int)ret;
}

//assert(c == '\n');
assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}

}

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int __gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}

const int hashmod=76543;
struct HaHashsh{
struct ss{int v;int w,last;}G;
int find(int a){
int A= a % hashmod;
if(G[i].v==a)return G[i].w;
return -1;
}
void insert(int a,int b){
int A= a % hashmod;
}
}hs;

using ll = long long;

ll discreteLog(ll a,ll b,ll MOD) {
a = a%MOD; b = b%MOD;
if (b == 1) return 0;

for(int x = 1 % MOD, k = 0; k <= 10000; k++) {
if(x == b) return k;
x = ((long long)x * a) % MOD;
}

int cnt = 0;
ll t = 1;
for (ll g = __gcd(a,MOD);g != 1;g = __gcd(a,MOD)) {
if (b%g) return -1; //
MOD /= g,b /= g;
t = t*a/g%MOD;
cnt ++;// x -> x1
if (t == b) return cnt; //b1 = 1
}
hs.clear();
int m = ceil(sqrt(1.0*MOD));
ll e = 1;
std::unordered_set<ll> chk;
for (int i = 0;i < m;i ++) { //a^i i = [0,sqrt(m)) b*a^i
ll v = e*b%MOD;
if(chk.count(v) == 0) {
hs.insert(v, i);
chk.insert(v);
}
e = e*a%MOD;
}
ll nw = t;
ll ans = -1;
for (int i = 1;i <= m+1;i ++) {
nw = e*nw%MOD;
int v = hs.find(nw);
if (v != -1) {
if(ans == -1 || ans > i*m-v+cnt) ans = i*m-v+cnt;
}
}
return ans;
}

long long my_pow(long long a, long long n, long long mod) {
if(n == 0) return 1 % mod;
if(n % 2 == 1) return my_pow(a, n - 1, mod) * a % mod;
return my_pow(a * a % mod, n / 2, mod);
}

void run() {
std::string N;
while(!seekEof() && isdigit(seekChar())) N += readChar();
assert(X < M);
assert(N != '0');
assert(N.length() <= 10000 || (N.length() == 10001 && N == '1' && std::count(N.begin(), N.end(), '0') == 10000));

if(M == 1 || X == 1) {
printf("0\n");
return;
}

const int MOD = 998244353;

// 2^1375 = (2^137)^10 * 2^5
long long base = 1;
long long pow2n = 1;
for(char c : N) {
base = (my_pow(base, 10, M) * my_pow(2, c - '0', M)) % M;
pow2n = (my_pow(pow2n, 10, MOD) * my_pow(2, c - '0', MOD)) % MOD;
}
base = (base - 1 + M) % M;

long long popcount = discreteLog(base, X, M);
long long ans = -1;
if(popcount != -1) {
ans = (my_pow(2, popcount, MOD) - 1 + MOD) % MOD;
ans = (ans * pow2n) % MOD;
ans = (ans * my_pow(2, MOD-2, MOD)) % MOD;
}
printf("%lld\n", ans);
}

int main() {
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
freopen("input.txt", "r", stdin);
#endif

while(T--) {
run();
}
return 0;
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int M=998244353, I2=499122177;
string n;
int x, m;

ll bsgs(ll g, ll t, ll m) {
ll sp=1%m, pn=64-__builtin_clzll(m);
for(ll i=0; i<pn; ++i, sp=sp*g%m)
if(sp==t)
return i;
ll d=__gcd(sp, m);
if(__gcd(t, m)^d)
return -1;
ll b=1, gp=g;
for(; b*b<m; ++b)
gp=gp*g%m;
unordered_map<ll, ll> mp;
for(ll i=1, p=t*g%m; i<=b; ++i, p=p*g%m)
mp[p]=i;
for(ll i=1, p=sp*gp%m; i<=b; ++i, p=p*gp%m)
if(mp.find(p)!=mp.end())
return i*b-mp[p]+pn;
return -1;
}

ll pm(ll b, ll p, ll m) {
ll r=1;
for(; p; p/=2, b=b*b%m)
if(p&1)
r=r*b%m;
return r;
}

ll pm2(ll b, string p, ll m) {
//b^1234 = (b^123)^10*b^4
ll r=1;
for(char c : p)
r=pm(r, 10, m)*pm(b, c-'0', m)%m;
return r;
}

void solve() {
cin >> n >> x >> m;
if(!x&&n!="1") {
cout << 1%m << "\n";
return;
}
//(2^n-1)^popcount = x mod m
ll b=(pm2(2, n, m)+m-1)%m, pc=bsgs(b, x, m);
if(pc<0) {
cout << "-1\n";
return;
}
//2^(n-1)*(2^(popcount)-1)
cout << pm2(2, n, M)*I2%M*(pm(2, pc, M)+M-1)%M << "\n";
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int t;
cin >> t;
while(t--)
solve();
}


Please give me suggestions if anything is unclear so that I can improve. Thanks 2 Likes

What value F(2,1) has? I think it is equal to 3 as [0, 1], [1,0] and [1, 1] have beauty 1. So why the correct solutions give answer “1” to query (2, 0, 2)? Am I missing something?

Because there are 0 ways and 0 mod 2 is 0.
Those have beauty 2.

this trap is responsible for most WAs XD…

When N \ge 2, X = 0 and M \ge 2, the answer should be 1.

I found this trap, THREE HOURS after I wrote BSGS algorithm correctly!  1 Like

It took me 3 days to find it lol😛

so sad at least you found it

1 Like

Want to know what is more sad?
This…

idk why my solution doesn’t work for 2 tc?

1 Like

I was also getting these test cases wrong but got ac when i realized a silly mistake in my bsgs algo

1 Like

[0, 1], [1, 0], [1, 1] have beauties 2.

1 Like

I had around 30 WA submissions “fixing” my already correct BSGS, only to find this hack case.

1 Like

Can you tell me which mistake.?
I am dying to know!

This problem tempted me to join. Couldn’t fix one of bug/corner case even after ~100 submissions. Rage quit.   3 Likes

Here’s the code with the bug fixed.

On line 23 of your code, replacing the abomination of a line

t=int(int(int(t*a)/g)%p)


with

t = t * a // g % p


does the trick. It probably comes from a precision error when performing floating point division.

1 Like

Thanks a lot for your kind help!!  Finished and updated

3 Likes

Why is this true? Thanks

I did include the proof…

Also, it is pretty simple to google search, just a piece of advice when you’re reading an editorial which does not include explanations for such things

Can someone please explain it in a more comprehensible way?

For X=0, I think in cases, where there is no F(N,B) which will give a remainder 0 after dividing by M, wouldn’t the answer be simply -1 as there is no valid B. And in cases where it can give remainder 0, we will display the required beauty.

For x=0 case

Let us first assume b=0 (minimum possible), we get f(n,b)=1 (\forall n>=1) and we want 1\%m=0 . Now let us look at possible cases where we can get 1\%m=0 and this is only if m=1 and no for other value.
So, x=0 and b=0 , if and only if, m=1

Case where m!=1

Okay, so now we have x=0 and m>1.
Consider n=1 so, f(n,b)=1(\forall b>=0). So, we want to satisfy the equation 1\%m=0 which is not possible for m>1 and hence b=-1.

Consider n>1

We can’t have b=0 (\text{as} \ m>1). Try b=1. If b=1, f(n,b)=0(\forall n>1) [note that if b=1 and n=1, then f(n,b)=1]. We want f(n,b)\%m=0 and f(n,b)=0. So, this equation is valid \forall m>1 and this is what we wanted. Hence, b=1 is the case when n>1,x=0 \text{and}\ m>1.

1 Like