INVXOR - Editorial

PROBLEM LINK:

Practice
Div-1 Contest

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

DIFFICULTY:

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[10];
int32_t main()
{
    ios_base::sync_with_stdio(0);
    int invof2 = qpow(2, mod - 2, mod);
    pw[0] = 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);
    vals.max_load_factor(0.25);
    while(t--){
        string s; cin >> s;
        assert(s[0] != '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[0] == '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 readChar() {
    char ret = seekChar();
    _buf_pos++;
    return ret;
}
 
int readInt(int lb, int rb) {
    char c = readChar();
    int mul = 1;
    if(c == '-') {
        c = readChar();
        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;
}
 
void readEoln() {
    char c = readChar();
    //assert(c == '\n');
    assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
 
void readSpace() {
    assert(readChar() == ' ');
}
 
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);
}
 
// copied from https://codeforces.com/gym/101853/submission/51466194, not sure about license
const int hashmod=76543;
struct HaHashsh{
    int head[hashmod],p;
    struct ss{int v;int w,last;}G[77000];
    void clear(){memset(head,0,sizeof(head));p=0;}
    int find(int a){
        int A= a % hashmod;
        for(int i=head[A];i;i=G[i].last)
            if(G[i].v==a)return G[i].w;
        return -1;
    }
    void insert(int a,int b){
        int A= a % hashmod;
        G[++p]=(ss){a,b,head[A]};head[A]=p;
    }
}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();
    readSpace();
    int X = readInt(0, 1000000000);
    readSpace();
    int M = readInt(1, int(1e9));
    assert(X < M);
    assert(N[0] != '0');
    assert(N.length() <= 10000 || (N.length() == 10001 && N[0] == '1' && std::count(N.begin(), N.end(), '0') == 10000));
    //readEoln();
 
    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
 
    int T = readInt(1, 100);
    readEoln();
 
    while(T--) {
        run();
        if(T > 0) readEoln();
    }
    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 :slight_smile:

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! :upside_down_face: :angry:

1 Like

It took me 3 days to find it lol😛

so sad :rofl:

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. :angry::angry::angry:

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!! :blush::blush:

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