PROBLEM LINK:
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 
