Sum Over Subsets Codeforces Round #678 SOLUTION

by

F. Sum Over Subsets Codeforces Round #678 SOLUTION

You are given a multiset S. Over all pairs of subsets A and B, such that:
B⊂A;
|B|=|A|−1;
greatest common divisor of all elements in A is equal to one;
find the sum of ∑x∈Ax⋅∑x∈Bx, modulo 998244353.
Input
The first line contains one integer m (1≤m≤105): the number of different values in the multiset S.
Each of the next m lines contains two integers ai, freqi (1≤ai≤105,1≤freqi≤109). Element ai appears in the multiset S freqi times. All ai are different.
Output
Print the required sum, modulo 998244353.
Examples
inputCopy
2
1 1
2 1
outputCopy
9
inputCopy
4
1 1
2 1
3 1
6 1
outputCopy
1207
inputCopy
1
1 5
outputCopy
560
Note
A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.
A⊂B: Set A is a subset of a set B.
In the first example B={1},A={1,2} and B={2},A={1,2} have a product equal to 1⋅3+2⋅3=9. Other pairs of A and B don’t satisfy the given constraints.
SOLUTION :
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int mod = (int) 1e9 + 7;
 
int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) {
      r = (ll) r * a % mod;
    }
    a = (ll) a * a % mod;
    b /= 2;
  }
  return r;
}
 
 
const int M = mod;
 
int add(int a, int b) {
  a += b;
  if (a >= M) return a – M;
  if (a < 0) return a + M;
  return a;
}
 
int mul(int a, int b) {
  return a * (ll) b % M;
}
 
int dv(int a, int b) {
  return mul(a, pw(b, M – 2));
}
 
int sqr(int x) {
  return mul(x, x);
}
 
const int N = (int) 2e5 + 7;
int f[N];
 
int c(int n, int k) {
  if (!(0 <= k && k <= n)) {
    assert(0);
  }
  return dv(f[n], mul(f[k], f[n – k]));
}
 
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  ///freopen (“input”, “r”, stdin);
 
  f[0] = 1;
  for (int i = 1; i < N; i++) f[i] = mul(f[i – 1], i);
 
  int m;
  cin >> m;
  vector<int> a;
  for (int i = 1; i <= m; i++) {
    int x, f;
    cin >> x >> f;
    for (int j = 1; j <= f; j++) a.push_back(x);
  }
  int n = (int) a.size(), sol = 0;
  for (int m = 1; m < (1 << n); m++) {
    int g = 0;
    for (int i = 0; i < n; i++) if (m & (1 << i)) g = __gcd(g, a[i]);
    if (g == 1) {
      vector<int> e;
      int su = 0, cnt = 0;
      for (int i = 0; i < n; i++) {
        if (m & (1 << i)) {
          e.push_back(a[i]);
          su = add(su, a[i]);
          cnt++;
        }
      }
      sol = add(sol, mul(cnt – 1, sqr(su)));
    }
  }
  cout << sol << “n”;
}

Leave a Comment