#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1000'000'000,b = 1000'000'000;
  long long product = a * b;
  cout << product << '\n';
  return 0;
}

Overflow!

Even if you declared the product variable as long long, what's happening, in reality, is, first the compiler is multiplying a with b and then it is assigning the output to the product variable and as a and b both are int, that's why the output is also int, but $$$10^{18}$$$ is too much to contain for an int variable.

So how to solve this?

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1000'000'000,b = 1000'000'000;
  long long product = (long long) a * b;
  cout << product << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int get_size(vector<int> a) {
  return (int)a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

Nope! The complexity is actually $$$O(n^2)$$$.

This is because you are passing the vector by value — meaning every time you are calling the function the whole vector of $$$10^6$$$ elements is getting passed in the function. So how to solve this?

#include<bits/stdc++.h>
using namespace std;

int get_size(vector<int> &a) {
  return (int)a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(N, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // it is guaranteed that total sum of n is <= 100000
  return 0;
}

It's not $$$100000$$$. It's actually around $$$10^{10}$$$ as every time you are declaring a vector of size $$$10^5$$$. I used to do this mistake a lot in the beginning. How to solve this?

#include<bits/stdc++.h>
using namespace std;

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(n, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // it is guaranteed that total sum of n is <= 100000
  return 0;
}

Also, check this out.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 5;
  int a[n];
  memset(a, 1, sizeof a);
  for (int i = 0; i < n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  return 0;
}

memset function is actually for char or 1 byte data types! Check out this to learn more.

Then you might ask I have seen people doing memset(a, -1, sizeof a) or memset(a, 0, sizeof a). Well, that's because it works for $$$0$$$ and $$$-1$$$ accidentally! Check out this comment to learn why memset works for $$$0$$$ and $$$-1$$$ correctly.

Using memset to set all elements in an array to $$$-1$$$ or $$$0$$$ is cool as it works really faster than just looping through all the indices and setting them to $$$-1$$$ or $$$0$$$. But be careful while using it for other numbers.

smash me

Don't use pow() unless you are bound to use this because sometimes the answer won't be exactly what you are expecting, and there will be slight precision errors. For example, it's clear that log2(1 << 30) is $$$30$$$. But sometimes it may consider it as $$$29.9999999999999$$$ and when converting it to int, it will return 29.

Similar to this, as pow() takes double as arguments, pow(5, 2) should return $$$5^2=25.00$$$, but sometimes it may consider it as $$$24.9999999999999$$$ and when converting it to int, it will return $$$24$$$. You may use round(pow(5, 2)) in this particular case to avoid the precision issue or just brute force.

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v;
  cout << v.size() - 1 << '\n';;
  return 0;
}

Check this out. Or in short, v.size() acts more like unsigned data types.

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v;
  cout << (int)v.size() - 1 << '\n';;
  return 0;
}

That's why the following code will run indefinitely.

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v;
  for (int i = 0; i < v.size() - 1; i++) { // use i < (int)v.size() - 1 here
    // do something
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i <= 3; i++) {
    cout << i << '\n';
    printf("%d\n", i + 10);
  }
  return 0;
}

1
11
2
12
3
13

1
2
3
11
12
13

That's because the synchronization has been turned off using the line ios_base::sync_with_stdio(0). Check this out to know more.

So do not mix C-style and C++-style printers after using ios_base::sync_with_stdio(0).

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1, b = 3;
  // we want to take b & 3 and add it to a
  int result = a + b & 3;
  cout << result << '\n';
  return 0;
}

The precedence of the + operator is higher than the & operator, so the operator + operates first, meaning a+b = 4 executes and then the & operator comes into play, so 4&3 executes and the output is clearly 0 for this.

Check out this to learn more about C++ operator precedence.

So how to solve this issue?

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1, b = 3;
  // we want to take b & 3 and add it to a
  int result = a + (b & 3);
  cout << result << '\n';
  return 0;
}

Another similar classic error is 1 << n - 1 is not $$$2^{n}-1$$$, it's actually $$$2^{n-1}$$$ as - has more precedence than the << operator.

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e6;
int main() {
  int minimum = INF;
  for (int i = 1; i <= 10; i++) {
    int x; cin >> x; // the value of x can be up to 10000
    minimum = min(minimum, x * x);
  }
  cout << minimum << '\n';
  return 0;
}

Beginners sometimes don't care about the INF value. For example, here the value of x can be up to $$$10000$$$, meaning the value of x*x, will be up to $$$10^8$$$. But here the value of the minimum variable has been set to $$$10^6$$$, which is not large enough.

So always make sure that the initialized value of a variable is large enough (or small enough).

#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int> mp;
int main() {
  int n = 300000;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    mp[x]++;
  }
  int max_occurrence = 0;
  for (auto [val, cnt]: mp) {
    max_occurrence = max(max_occurrence, cnt);
  }
  cout << max_occurrence << '\n';
  return 0;
}

Because of unordered map! The worst-case time complexity of our code is $$$O(n^2)$$$, that's because unordered map is a hash map and it might take more than $$$O(1)$$$ operations to insert or access in case of the input is not random.

Check this post: Blowing up unordered_map, and how to stop getting hacked on it

So always use a custom hash if you don't want to get blown up.

#include<bits/stdc++.h>
using namespace std;

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // now erase one occurrence of 2
  se.erase(2);
  // now print the elements
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  return 0;
}

That's because if you use a value in the erase() function in a multiset, then all elements will be erased, but if you erase an iterator, then only the element in that iterator will get erased. Check this out for more.

#include<bits/stdc++.h>
using namespace std;

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // now erase one occurrence of 2
  se.erase(se.find(2));
  // now print the elements
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  // 1 1 2 2 3 4 5 5 
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> mp;
  // add 1 to 5 to the map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // check how many numbers from 1 to 10 exist in the map
  for (int i = 1; i <= 10; i++) {
    if (mp[i]) {
      ++cnt;
    }
  }
  // now print the size of the map
  cout << (int)mp.size() << '\n';
  return 0;
}

No! It's actually $$$10$$$.

That's because of the statement if (mp[i]), mp[i] also inserts the element i into the map even if it doesn't exist. This type of error might get you some unexpected MLEs.

But how to solve this?

#include<bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> mp;
  // add 1 to 5 to the map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // check how many numbers from 1 to 10 exist in the map
  for (int i = 1; i <= 10; i++) {
    if (mp.find(i) != mp.end()) {
      ++cnt;
    }
  }
  // now print the size of the map
  cout << (int)mp.size() << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // compute the sum of 1 to n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // get the iterator containing the smallest element >= i 
    // it will point to i here
    auto it = lower_bound(se.begin(), se.end(), i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Wrong!

It's actually $$$O(n^2)$$$. Wait, but doesn't lower_bound work in $$$O(\log{n})$$$?

Actually lower_bound(set.begin(), set.end(), value) is not $$$O(\log{n})$$$! Check out this to learn more.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // compute the sum of 1 to n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // get the iterator containing the smallest element >= i 
    // it will point to i here
    auto it = se.lower_bound(i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Same for upper_bound.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s = s + 'a'; // append a to the string
  }
  cout << s << '\n';
  return 0;
}

It's not $$$O(n)$$$! It's $$$O(n^2)$$$ actually.

Because every time you are using s = s + 'a', on the right side it is accessing the whole string s (which can be $$$O(n)$$$ in size). How to fix this?

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s += 'a'; // append a to the string
  }
  cout << s << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  int test_cases; cin >> test_cases;
  // take an array of length n as input
  // print YES if the length is 1 or NO otherwise!
  while (test_cases--) {
    int n; cin >> n; // length of the array
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) { // taking the array elements as input
      cin >> a[i];
    }
    cout << "NO\n";
  }
  return 0;
}

When n == 1, you are continuing even before taking the array as input. So the code will give WA in some cases.

2
1
1
2
1 3

It happened to me multiple times before! So please take the whole input first if you want to continue by checking some base cases.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int test_cases; cin >> test_cases;
  // take an array of length n as input
  // print YES if the length is 1 or NO otherwise!
  while (test_cases--) {
    int n; cin >> n; // length of the array
    vector<int> a(n);
    for (int i = 0; i < n; i++) { // taking the array elements as input
      cin >> a[i];
    }
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    cout << "NO\n";
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
  int test_cases; cin >> test_cases;
  while (test_cases--) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
      int x; cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';
  }
  return 0;
}

Notice that the problem has multiple test cases. But you are not resetting the cnt array in each test! So the counts of previous test cases will still be in the cnt array and will produce WA.

2
1
1
1
2

So always clear everything from the previous tests.

#include<bits/stdc++.h>
using namespace std;

const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
  int test_cases; cin >> test_cases;
  while (test_cases--) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
      int x; cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';

    // resetting everything
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      cnt[i] = 0;
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int main() {
  int a = 1e9, b = 1e9, c = 1e9;
  int sum = (a + b + c) % mod;
  cout << sum << '\n';
  int product = a * b % mod;
  cout << product << '\n';
  int random = 1LL * a * (b * c % mod) % mod;
  cout << random << '\n';
  a = 1e8;
  int sub = (a - b) % mod; 
  cout << sub << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int main() {
  // 0 <= a, b, c < mod
  int a = 1e9, b = 1e9, c = 1e9;

  int sum = (a + b + c) % mod; 
  // overflow as (a + b + c) > INT_MAX(=2147483647)
  // better way: ((a + b) % mod + c) % mod
  cout << sum << '\n';

  int product = a * b % mod;
  // overflow as a * b > INT_MAX
  // better way: 1LL * a * b % mod
  cout << product << '\n';

  int random = 1LL * a * (b * c % mod) % mod; 
  // overflow in the (b * c % mod) part
  // correct way: 1LL * a * (1LL * b * c % mod) % mod
  // better way: 1LL * a * b % mod * c % mod
  cout << random << '\n';

  a = 1e8;
  int sub = (a - b) % mod; 
  // not overflow, but when a < b, it will produce a negative number
  // better way: (a - b + mod) % mod
  cout << sub << '\n';

  // Also always make sure that after each arithmetic operation
  // All of your variables are in the range [0, mod-1]
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  long long val= 1e12;
  vector<long long> v({val, val, val});
  // now take sum of all elements
  long long sum = accumulate(v.begin(), v.end(), 0);
  cout << sum << '\n';
  return 0;
}

That's because the initialized variable (0) is an int, so the sum also returns as int. Check this out for more.

#include<bits/stdc++.h>
using namespace std;

int main() {
  long long val= 1e12;
  vector<long long> v({val, val, val});
  // now take sum of all elements
  long long sum = accumulate(v.begin(), v.end(), 0LL); // typecast
  cout << sum << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<double> v({1.23, 2.05, 3.003});
  // now take sum of all elements
  double sum = accumulate(v.begin(), v.end(), 0); // correct way: 0.0
  cout << sum << '\n'; // it outputs 6 which is not intended
  return 0;
}

long long x = (long long)1e18 - 1;
long long k = sqrtl(x);
while (k * k < x) ++k;
while (k * k > x) --k;
cout << k << '\n';

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 100000;
  multiset<int> se;
  // insert n instances of 1
  for (int i = 1; i <= n; i++) {
    se.insert(1);
  }
  long long tot = 0;
  // let's count how many 1s are there in the multiset, n times
  for (int i = 1; i <= n; i++) {
    tot += se.count(1);
  }
  cout << tot << '\n';
  return 0;
}

It's not $$$O(n \, \log{n})$$$, it's actually $$$O(n^2)$$$!

Why? Because the time complexity is logarithmic in the size of the container + linear in the number of occurrences of the element and here, the occurrence of $$$1$$$ is $$$n$$$. So use the count() function for multisets carefully!

Also, if you want to check if a number exists in a multiset use the find() function instead of counting the occurrences.

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      int k; cin >> k;
      ans = max(ans, k - i);
    }
    cout << ans << '\n';
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<int> a(n + 1);
    bool inc = true;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      inc &= a[i] > a[i - 1];
    }
    if (n % 2 == 0 or !inc) {
      cout << "YES\n";
    }
    else {
      cout << "NO\n";
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    bool ok = true;
    for (int i = 1; i <= n; i++) {
      int x; cin >> x;
      bool found = false;
      for (int j = i + 1; j >= 2; j--) { // this loop will run not more than 22 times, in practice its much lower than that
        if (x % j) {
          found = true;
          break;
        }
      }
      ok &= found;
    }
    if (ok) {
      cout << "YES\n";
    }
    else {
      cout << "NO\n";
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int x, y; cin >> x >> y;
    if (x <= y) {
      cout << y - y % x / 2 << '\n';
    }
    else {
      cout << x + y << '\n';
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9, mod = 998244353;
vector<int> v[2];
int dp[2][N];
int a[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    long long ans = 0;
    for (int i = n; i >= 1; i--) {
      int k = i & 1;
      v[k].push_back(a[i]);
      dp[k][a[i]] = 1;
      int last = a[i];
      for (auto x: v[k ^ 1]) {
        int y = dp[k ^ 1][x];
        int split = (a[i] + x - 1) / x;
        int st = a[i] / split;
        ans += 1LL * (split - 1) * y * i;
        dp[k][st] += y;
        if (last != st) {
          v[k].push_back(st), last = st;
        }
      }
      for (auto x: v[k ^ 1]) dp[k ^ 1][x] = 0;
      v[k ^ 1].clear();
      ans %= mod;
    }
    cout << ans << '\n';
    for (auto x: v[0]) dp[0][x] = 0;
    for (auto x: v[1]) dp[1][x] = 0;
    v[0].clear(); v[1].clear();
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9;
const long long inf = 1e12;
using ll = long long;
int phi[N];
void totient() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++) {
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  }
}
ll a[N], s1[N][320], s2[N][320];
int root[N];
ll c(int l, int r) {
  if (l > r) return inf;
  ll ans = 0;
  if (r / l <= root[r]) {
    return s1[r][r / l] - a[r / l] * (l - 1 - r / ((r / l) + 1));
  }
  else {
    return s2[r][l];
  }
  return ans;
}
ll dp[N][17];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  totient();
  for (int i = 1; i < N; i++) {
    a[i] = a[i - 1] + phi[i];
  }
  for (int i = 1; i < N; i++) {
    root[i] = 0;
    for (int j = 1; j * j <= i; j++) {
      s1[i][j] = s1[i][j - 1] + a[j] * (i / j - i / (j + 1));
      root[i] = j;
    }
    s2[i][i / (root[i] + 1) + 1] = s1[i][root[i]];
    for (int j = i / (root[i] + 1); j >= 1; j--) {
      s2[i][j] = s2[i][j + 1] + a[i / j];
    }
  }
  int n = 100000;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = inf;
  }
  for (int k = 1; (1 << k) <= n; k++) {
    dp[0][k] = 0;
    vector<pair<int, int> > v; // (start pos, best j)
    v.push_back(make_pair(0, 0));
    for (int x = 1; x <= n; x++) {
      int j = (--lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)))->second;
      dp[x][k] = dp[j][k - 1] + c(j + 1, x);
      for (int i = (int)v.size() - 1; i >= 0; i--) {
        int y = v[i].first, oldj = v[i].second;
        if (y > x && dp[x][k - 1] + c(x + 1, y) < dp[oldj][k - 1] + c(oldj + 1, y)) v.pop_back();
        else {
          int l = y + 1, r = n + 1;
          while (l < r) {
            int mid = (l + r) / 2;
            if (dp[x][k - 1] + c(x + 1, mid) < dp[oldj][k - 1] + c(oldj + 1, mid)) r = mid;
            else l = mid + 1;
          }
          if (r != n + 1) v.push_back(make_pair(r, x));
          break;
        }
      }
      if (v.size() == 0) v.push_back(make_pair(0, x));
    }
  }
  int q; cin >> q;
  while (q--) {
    int n, k; cin >> n >> k;
    if (k >= 20 or (1 << k) > n) {
      cout << n << '\n';
    }
    else {
      cout << dp[n][k] << '\n';
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9;
const long long inf = 1e12;
using ll = long long;
int phi[N];
void totient() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++) {
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  }
}
ll a[N];
ll c(int l, int r) {
  if (l > r) return inf;
  ll ans = 0;
  for (int i = l, last; i <= r; i = last + 1) {
    last = r / (r / i);
    int x = 0;
    if (i >= l) x = last - i + 1;
    else if (last >= l) x = last - l + 1;
    ans += a[r / i] * x;
  }
  return ans;
}
ll dp[N][17];
void yo(int i, int l, int r, int optl, int optr) {
  if(l > r) return;
  int mid = (l + r) / 2;
  dp[mid][i] = inf;
  int opt = optl;
  ll cost = c(min(mid, optr) + 1, mid);
  for(int k = min(mid, optr); k >= optl ; k--) {
    ll cc = dp[k][i - 1] + cost;
    if (cc <= dp[mid][i]) {
      dp[mid][i] = cc;
      opt = k;
    }
    if (k <= mid) {
      if (cost == inf) cost = a[mid / k];
      else cost += a[mid / k];
    }
  }
  yo(i, l, mid - 1, optl, opt);
  yo(i, mid + 1, r, opt, optr);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  totient();
  for (int i = 1; i < N; i++) {
    a[i] = a[i - 1] + phi[i];
  }
  int n = 100000;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = inf;
  }
  for(int i = 1; i <= n; i++) dp[i][1] = 1LL * i * (i + 1) / 2;
  for(int i = 2; i <= 16; i++) yo(i, 1, n, 1, n);
  int q; cin >> q;
  while (q--) {
    int n, k; cin >> n >> k;
    if (k >= 20 or (1 << k) > n) {
      cout << n << '\n';
    }
    else {
      cout << dp[n][k] << '\n';
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 205;
int mod;
 
int power(long long n, long long k) {
  int ans = 1 % mod; n %= mod; if (n < 0) n += mod;
  while (k) {
    if (k & 1) ans = (long long) ans * n % mod;
    n = (long long) n * n % mod;
    k >>= 1;
  }
  return ans;
}
int dp[N][N][40], fac[N], ifac[N];
int vis[N][N][40];
int n, a1;
/*
number of solutions to the equation b1 + b2 + ... bn <= a1
s.t. 0<=bi<=n+1-a1 
and there is at least 1 number >= n + 1 - a1, 
at least 2 numbers >= (n - a1), ..., at least (n - a1) numbers >= 2
*/
int yo(int i, int sum, int k) { // k <= 2 * sqrt(n)
  if (i == n) return fac[n];
  if (k == 0) return 1LL * fac[n] * ifac[n - i] % mod;
  if (vis[i][sum][k] == a1) return dp[i][sum][k];
  vis[i][sum][k] = a1;
  int &ans = dp[i][sum][k];
  ans = 0;
  int r = (a1 - sum) / k;
  for (int cnt = r; cnt >= 0; cnt--) {
    if (k > 1 and i + cnt < n - a1 + 1 - k + 1) continue;
    ans += 1LL * yo(i + cnt, sum + cnt * k, k - 1) * ifac[cnt] % mod;
    ans %= mod;
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> mod;
  fac[0] = 1;
  ifac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = 1LL * fac[i - 1] * i % mod;
    ifac[i] = power(fac[i], mod - 2);
  }
  int ans = 0;
  int lim = 2 * sqrt(n) + 1;
  for (a1 = max(1, n - lim); a1 <= n; a1++) {
    ans += yo(0, 0, n + 1 - a1);
    ans %= mod;
  }
  ans %= mod;
  cout << ans << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e7 + 9, mod = 998244353;
template <const int32_t MOD>
struct modint {
  int32_t value;
  modint() = default;
  modint(int32_t value_) : value(value_) {}
  inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
  inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
  inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
  inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
  inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
  inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
  inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
  modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
  modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
  inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
  inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
  inline bool operator == (modint<MOD> other) const { return value == other.value; }
  inline bool operator != (modint<MOD> other) const { return value != other.value; }
  inline bool operator < (modint<MOD> other) const { return value < other.value; }
  inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
using mint = modint<mod>;
 
mint pw[N];
mint genius(int n, int k) {
  if (k == 0) return 1;
  vector<mint> c(k, 0), d(k + 1, 0);
  d[k] = 1;
  for (int i = k - 1; i >= 0; i--) {
    c[i] = pw[i] * d[i + 1];
    d[i] = (pw[i] - 1) * d[i + 1];
  }
  mint ans = 0, pwn = mint(2).pow(n), cur = 1;
  for (int i = 0; i < k; i++) {
    ans += ((k - 1 - i) & 1 ? mod - 1 : 1) * c[i] * cur;
    cur *= pwn;
  }
  return ans;
}
mint f(int n, int k) {
  if (k == 0 or n > k) return 0;
  mint ans = 1;
  for (int i = 0; i < n; i++) {
    ans *= pw[k] - pw[i];
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  pw[0] = 1;
  for (int i = 1; i < N; i++) {
    pw[i] = pw[i - 1] * 2;
  }
  int t; cin >> t;
  while (t--) {
    int n, k, x; cin >> n >> k >> x;
    if (x) {
      cout << genius(n, k) << '\n';
    }
    else {
      cout << f(n, k) << '\n';
    }
  }
  return 0;
}

Details: here

Div2A - 0.005 USD
Div2B - 0.006 USD
Div2C/Div1A - 0.008 USD
Div2D/Div1B - 0.01 USD
Div2E/Div1C - 0.04 USD
Div2F/Div1D - 0.2 USD
Div1E - 2 USD
Div1F - 2 USD

Div2A - 0.005 * 9529 = 47.645 USD
Div2B - 0.006 * 6274 = 37.644 USD
Div2C/Div1A - 0.008 * (4012+967) = 39.832 USD
Div2D/Div1B - 0.01 * (2273+911) = 31.84 USD
Div2E/Div1C - 0.04 * (27+396) = 16.92 USD
Div2F/Div1D - 0.2 * (1+24) = 5 USD
Div1E - 2 * 8 = 16 USD
Div1F - 2 * 3 = 6 USD

Total - 200.881 USD

#include<bits/stdc++.h>
using namespace std;

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<int> a(n);
    for (auto &x: a) {
      cin >> x;
    }
    long long ans = 0;
    for (int i = 1; i < n; i++) {
      ans = max(ans, 1LL * a[i] * a[i - 1]);
    }
    cout << ans << '\n';
  }
  return 0;
}

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
  n = int(input())
  a = list(map(int, input().split()))
  ans = 0
  for i in range(n - 1):
    ans = max(ans, a[i] * a[i + 1])
  print(ans)

#include<bits/stdc++.h>
using namespace std;

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    long long ans = -1e12;
    int l = max(1, n - 2 * k);
    for (int i = l; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
        ans = max(ans, 1LL * i * j - 1LL * k * (a[i] | a[j]));
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
  n, k = map(int, input().split())
  a = list(map(int, input().split()))
  l = max(0, n - 2 * k - 1)
  ans = -1e12
  for i in range(l, n):
    for j in range(i + 1, n):
      ans = max(ans, (i + 1) * (j + 1) - k * (a[i] | a[j]))
  print(ans)

#include<bits/stdc++.h>
using namespace std;

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n, m; cin >> n >> m;
    ++m;
    int ans = 0;
    for (int k = 30; k >= 0 and n < m; k--) {
      if ((n >> k & 1) == (m >> k & 1)) continue;
      if (m >> k & 1) ans |= 1 << k, n |= 1 << k;
    }
    cout << ans << '\n';
  }
  return 0;
}

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  m += 1
  ans = 0
  for k in range(30, -1, -1):
    if (n >= m): break
    if ((n >> k & 1) == (m >> k & 1)): continue
    if (m >> k & 1):
      ans |= 1 << k
      n |= 1 << k
  print(ans)

#include<bits/stdc++.h>
using namespace std;

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    if (n == 1) {
      cout << "a\n";
    }
    else {
      cout << string(n / 2, 'a') + (n & 1 ? "bc" : "b") + string(n / 2 - 1, 'a') << '\n';
    }
  }
  return 0;
}

t = int(input())
for _ in range(t):
  n = int(input())
  if (n == 1):
    print('a')
  else:
    s = 'a' * (n // 2)
    if (n & 1):
      s += 'bc'
    else:
      s += 'b'
    s += 'a' * (n // 2 - 1)
    print(s)

Write a suffix automata and check if every node occurs an odd number of times.

#include<bits/stdc++.h>
#include "testlib.h"
using namespace std;

// len -> largest string length of the corresponding endpos-equivalent class
// link -> longest suffix that is another endpos-equivalent class.
// firstpos -> 1 indexed end position of the first occurrence of the largest string of that node
// minlen(v) -> smallest string of node v = len(link(v)) + 1
// terminal nodes -> store the suffixes
struct SuffixAutomaton {
  struct node {
    int len, link, firstpos;
    map<char, int> nxt;
  };
  int sz, last;
  vector<node> t;
  vector<int> terminal;
  vector<int> dp;
  vector<vector<int>> g;
  SuffixAutomaton() {}
  SuffixAutomaton(int n) {
    t.resize(2 * n); terminal.resize(2 * n, 0);
    dp.resize(2 * n, -1); sz = 1; last = 0;
    g.resize(2 * n);
    t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;
  }
  void extend(char c) {
    int p = last;
    int cur = sz++;
    t[cur].len = t[last].len + 1;
    t[cur].firstpos = t[cur].len;
    p = last;
    while (p != -1 && !t[p].nxt.count(c)) {
      t[p].nxt[c] = cur;
      p = t[p].link;
    }
    if (p == -1) t[cur].link = 0;
    else {
      int q = t[p].nxt[c];
      if (t[p].len + 1 == t[q].len) t[cur].link = q;
      else {
        int clone = sz++;
        t[clone] = t[q];
        t[clone].len = t[p].len + 1;
        while (p != -1 && t[p].nxt[c] == q) {
          t[p].nxt[c] = clone;
          p = t[p].link;
        }
        t[q].link = t[cur].link = clone;
      }
    }
    last = cur;
  }
  void build_tree() {
    for (int i = 1; i < sz; i++) g[t[i].link].push_back(i);
  }
  void build(string &s) {
    for (auto x: s) {
      extend(x);
      terminal[last] = 1;
    }
    build_tree();
  }
  int cnt(int i) { // number of times i-th node occurs in the string
    if (dp[i] != -1) return dp[i];
    int ret = terminal[i];
    for (auto &x: g[i]) ret += cnt(x);
    return dp[i] = ret;
  }
};
pair<int, int> ok(string s) {
  int n = s.size();
  SuffixAutomaton sa(n);
  sa.build(s);
  for (int i = 1; i < sa.sz; i++) {
    if (sa.cnt(i) % 2 == 0) {
      return {sa.t[i].firstpos - sa.t[i].len, sa.t[i].firstpos - 1};
    }
  }
  return {-1, -1};
}
int main(int argc, char* argv[]) {
  registerTestlibCmd(argc, argv);
  int t = inf.readInt();
  inf.readEoln();
  for (int test = 1; test <= t; test++) {
    setTestCase(test);
    int n = inf.readInt();
    inf.readEoln();
    string s = ouf.readToken();
    if (s.size() != n) {
      quitf(_wa, "the length of s should be exactly %d", n);
    }
    for (int i = 0; i < n; i++) {
      if (!(s[i] >= 'a' and s[i] <= 'z')) {
        quitf(_wa, "s contains %c which is not an English lowercase character", s[i]);
      }
    }
    auto p = ok(s);
    if (p.first != -1) {
      quitf(_wa, "the substring s[%d, %d] (0-indexed) occurs even number of times in s :\"(", p.first, p.second);
    }
  }
  quitf(_ok, "you are the best problem solver ever UwU");
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 9, mod = 998244353;

vector<int> g[N];
int dp[N], d, ok, ans[N];
void dfs(int u, int p = 0) {
  if (!ok) return;
  for (auto v: g[u]) {
    if (v ^ p) {
      dfs(v, u);
    }
  }
  if (dp[u] % d != 0) {
    if (p) {
      dp[u]++;
    }
    if (dp[u] % d != 0) {
      ok = 0;
      return;
    }
  }
  else {
    dp[p]++;
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
      ans[i] = 0;
    }
    ans[1] = 1;
    for (int k = 1; k <= n - 1; k++) {
      ans[1] = (ans[1] + ans[1]) % mod;
    }
    for (d = 2; d <= n - 1; d++) {
      if ((n - 1) % d == 0) {
        ok = 1;
        dfs(1);
        ans[d] = ok;
        for (int i = 0; i <= n; i++) {
          dp[i] = 0;
        }
      }
    }
    for (int i = n; i >= 1; i--) {
      for (int j = i + i; j <= n; j += i) {
        ans[i] = (ans[i] - ans[j] + mod) % mod;
      }
    }
    for (int i = 1; i <= n; i++) {
      if (i > 1) cout << ' ';
      cout << ans[i];
    }
    cout << '\n';
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
  }
  return 0;
}

Suffix Array of an integer sequence $$$a_1, a_2, \ldots, a_n$$$ is a permutation $$$p$$$ of size $$$n$$$ where $$$p_i$$$ refers to the suffix starting from index $$$p_i$$$ in $$$a$$$ and all suffixes are in sorted order. So suffix array of $$$[3, 1, 1, 2]$$$ is $$$[2, 3, 4, 1]$$$. It's basically a normal suffix array but here we have an integer sequence.

You are given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. The graph doesn't contain multi edges or self-loops. You will select every edge and randomly give a direction to it. What is the probability of creating a cycle?

Constraints: $$$1 \leq n \leq 100,$$$ $$$1 \leq m \leq \frac{n * (n - 1)}{2}$$$

You are given a graph with n nodes. The graph doesn't have any edge initially. You will select a random pair $$$(u, v), \; u \neq v$$$ and add a directed edge from $$$u$$$ to $$$v$$$. You will do it $$$k$$$ times. You may select the same edge multiple times. What is the probability of creating a cycle?

Constraints: $$$ 1 \leq n, \;k \leq 100$$$

You are given a graph with n nodes. The graph doesn't have any edge initially. You will select a random pair $$$(u, v), \; u \neq v$$$ and add a directed edge from $$$u$$$ to $$$v$$$. You will do it $$$k$$$ times. You can not select the same edge multiple times. What is the probability of creating a cycle?

Constraints: $$$ 1 \leq n, \;k \leq 100$$$

Here

Note that $$$m \geq 1$$$, so $$$(y+1) > c$$$. So we can say that $$$ (y+1) \; is \; composite: \; y \geq 1$$$

So $$$K^{th}$$$ value of $$$y$$$ is ($$$K^{th}$$$ composite number $$$-1$$$ ). How can we find it given that $$$K \leq 10^9$$$?

#include<bits/stdc++.h>
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 = 1e9 + 7;

const int MAX = 10000005;
bool prime[MAX];
int prec[MAX];
vector<int> P;

const int LIM = 250;
int memo[LIM*LIM][LIM];


ll rec(ll N, int K) {
  if (N <= 1 || K < 0) return 0;
  if (N <= P[K]) return N-1;
  if (N < MAX && P[K] * 1LL * P[K] > N) return N-1 - prec[N] + prec[P[K]];

  bool ok = N < LIM*LIM && K < LIM;
  if (ok && memo[N][K]) return memo[N][K];

  ll ret = N/P[K] - rec(N/P[K], K-1) + rec(N, K-1);

  if (ok) memo[N][K] = ret;
  return ret;
}

ll count_primes(ll N) {
  if (N < MAX) return prec[N];
  int K = prec[(int)sqrt(N) + 1];
  return N-1 - rec(N, K) + prec[P[K]];
}

void init_count_primes() {
  prime[2] = true;
  for (int i = 3; i < MAX; i += 2) prime[i] = true;

  for (int i = 3; i*i < MAX; i += 2)
    if (prime[i])
      for (int j = i*i; j < MAX; j += i+i)
        prime[j] = false;

  for(int i=2; i<MAX; i++) if (prime[i]) P.push_back(i);
  for(int i=1; i<MAX; i++) prec[i] = prec[i-1] + prime[i];
}
int32_t main()
{
    init_count_primes();
    int t; cin>>t;
    assert(1<=t<=20);
    while(t--){
        int k; cin>>k;
        assert(1<=k<=1000000000);
        ll l=1, r=2e9;
        ll ans=-1;
        while(l<=r){
            ll mid=(l+r)/2;
            if(mid-count_primes(mid)-1<k) l=mid+1;
            else ans=mid, r=mid-1;
        }
        assert(ans>0);
        cout<<ans-1<<nl;
    }
    return 0;
}

Giveaway. The answer is always the length of the given string.

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        cout<<s.size()<<endl;
    }

}

Let $$$X$$$ $$$=$$$ xor of all elements of $$$A$$$.

if $$$X$$$ $$$=$$$ $$$0$$$, output $$$-1$$$.

Otherwise, consider the largest set bit in $$$X$$$. Clearly this bit occurs an odd number of times in the whole array. So if we partition the array at the index where this bit occurs for the first time, then the right part will contain an even number of occurrence of that bit. So that bit will be off in the xor of the remaining elements. So we will have an optimal answer.

Using OR queries and binary search find the first element that has this bit set. Let's call it $$$k$$$. If $$$k$$$ $$$=$$$ $$$n$$$, output $$$-1$$$, otherwise output $$$k$$$.

So we will use at most $$$18$$$ queries.

#include<bits/stdc++.h>
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 = 1e9 + 7;


int32_t main()
{
    int n=in();
    cout<<2<<' '<<1<<' '<<n<<nl;
    cout.flush();
    int x; cin>>x;
    int b=-1;
    for(int i=30; i>=0; i--) if((x>>i)&1){
        b=i;
        break;
    }
    if(b==-1){
        cout<<"! -1\n";
        cout.flush();
        return 0;
    }
    int l=1, r=n-1, ans=-1;
    while(l<=r){
        int mid = (l+r)/2;
        cout<<1<<' '<<1<<' '<<mid<<nl;
        cout.flush();
        int o; cin>>o;
        if((o>>b)&1){
            ans=mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout<<"! "<<ans<<nl;
    cout.flush();
    return 0;
}

#include<bits/stdc++.h>
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 = 1e9 + 7;


int mp[50];
int get(int n)
{
    if(n==0) return 0;
    int i;
    for( i=31;i>=0;i--) if(n&(1<<i)) break;
    n-=(1<<i);
    ll ans=1LL*(i+1)*(n+1);
    return (ans+mp[i])%mod;
}
int32_t main()
{
    int i,j,k,n,m,t,l,r;
    for(i=1;i<32;i++){
        mp[i]=mp[i-1]+1LL*i*(1LL<<(i-1))%mod;
        mp[i]%=mod;
    }
    scanf("%d", &t);
    assert(t>=1&&t<=1e5);
    while(t--){
        scanf("%d %d", &l, &r);
        assert(l>=1&&l<=1e9);
        assert(r>=l&&r<=1e9);
        printf("%d\n", (get(r)-get(l-1)+mod)%mod);
    }
    return 0;
}

If there is a negative cycle then obviously no solution exists. Otherwise, set $$$P_i=$$$ the shortest path to the vertex $$$i$$$ from any vertex (including itself).

So we can use floyd-warshall or bellman-ford to solve the problem.

#include<bits/stdc++.h>
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 = 505;
const int mod = 1e9 + 7;

int ans[N];
int d[N][N];
int32_t main()
{
    int i,j,k,n,m,u,v,w;
    cin>>n>>m;
    assert(n>=2&&n<=500);
    assert(m>=1&&m<=min(n*(n-1),(int)1e5));
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) d[i][j]=1e9,d[i][i]=0;
    vector<pii> ed;
    vector<int> we;
    for(i=1;i<=m;i++){
        cin>>u>>v>>w;
        d[u][v]=w;
        ed.eb(u,v);
        we.eb(w);
        assert(u>=1&&u<=n);
        assert(v>=1&&v<=n);
        assert(w>=-1e5&&w<=1e5);
        assert(u!=v);
    }
    for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
    for(i=1;i<=n;i++) if(d[i][i]<0){
        cout<<"NO\n";
        return 0;
    }
    cout<<"YES\n";
    for(i=1;i<=n;i++) ans[i]=1e9;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) ans[j]=min(ans[j],d[i][j]);
    for(i=0;i<m;i++) assert(ans[ed[i].second]-ans[ed[i].first]<=we[i]);
    for(i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    return 0;
}
///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1

#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
using namespace std;
const double pi = 3.1416;

int main()
{
	int t;
	scanf("%d", &t);
	while(t--){
		int n;
		double l;
		scanf("%d %lf", &n, &l);
		assert(n >= 3);
		double sum = l;
		double nw = l;
		double angle = (n-2)*pi/n;
		double hehe = angle;
		double eqAngle = angle/(n-2);
		for(int i = 1; i<n-1; i++){
			double bahu = sqrt(nw*nw + l*l - cos(angle)*2.0*nw*l);
			sum += bahu;
			//cout << angle << endl;
			angle = hehe - (pi - angle - eqAngle);
			nw = bahu;
			// cout << bahu << " ... " << endl;
		}
		// cout << sum*2 << endl;
		// assert(fabs(nw-l) < 1e-3);
		printf("%.10f\n", (sum*n)/2.0 - ( n%2==1 ? 0: floor((n-2)/2)*l ));
	}	
	return 0;
}

Let

We can rewrite it as

Now the solution to our given product for some $$$l$$$ and $$$r$$$ is $$$\frac{F(r)}{F(l-1)}$$$

#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
#define mkp make_pair
#define all(a) a.begin(),a.end()
using namespace std;
ll bigmod(ll a, ll p){
	ll ret = 1;
	while(p){
		if(p&1) ret = ret * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return ret;
}
ll fact[2000]={682498929, 491101308, 76479948, 723816384, 67347853, 27368307, 625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362, 970055531, 261384175, 195888993, 66404266, 547665832, 109838563, 933245637, 724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623, 419363534, 500780548, 668123525, 128487469, 30977140, 522049725, 309058615, 386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327, 358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382, 703397904, 733333339, 97830135, 608823837, 256141983, 141827977, 696628828, 637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309, 456152084, 903466878, 92255682, 769795511, 373745190, 606241871, 825871994, 957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346, 671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561, 814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753, 172114298, 193781724, 778983779, 83868974, 315103615, 965785236, 492741665, 377329025, 847549272, 698611116};
ll multfact[2000]={611120140, 17897580,159967943,343237090,592951953,602244843,164013908,893236658,952101451,118482211,209920162,215152598,502381710,324159984,695459226,666860816,975716615,604726097,763034477,379041292,460748324,158354199,508213120,767279289,370470133,987651923,39242596,185475889,981761633,262769826,837005788, 681180371,661100686,908774984,38108703,396223792,793503000,819198011, 933664044,769608345,128783369,939038698,734053167,519165427,507816805,782246763,670871900,695337837,566025613,643867105, 476008438,909547109,980518787,678456808,218366494,992637363,7537905,20980780,379803548,410124767,587218502,463599811, 262065380,382170139,989269458,283943725,896112848,514669474,947602158,862475009,415829023,306830063,519359563,363545474, 758757919,497204956,969569909,39102155,126855068,631173350,6923144,794815151,253495907,554716148,685948839,513720461,309947752,492867651,326211127,657169128,464633342,764165057,613528541,579064017,114865160,794726205,431086582,512549494,460665448,34560};
const int lim = 10000000;
ll fun(ll n){
	// if(n < 1) return 1;
	if(n < lim) {
		ll ret = 1, mult = 1;
		for(int i = 1; i<=n; i++) {
			ret = ret * i % mod;
			mult = mult * ret % mod;
		}
		return bigmod(ret, n+2) * bigmod(mult, mod-2) % mod;
	}
	ll nfact = fact[n/lim-1];
	ll mult = multfact[n/lim-1];
	for(int i = (n/lim)*lim+1; i<=n; i++){
		nfact = nfact * i % mod;
		mult = mult * nfact % mod;
	}
	return bigmod(nfact, n+2) * bigmod(mult, mod-2) % mod;
}
int main()
{
	// ll fact = 1;
	// printf("ll fact[2000]={");
	// vector<int> vt;
	// ll mult = 1;
	// for(int i = 1; i<mod; i++){
	// 	fact = (fact * i) % mod;
	// 	mult = mult * fact % mod;
	// 	if(i%lim == 0){
	// 		vt.push_back(mult);
	// 		if(i/lim!=1) printf(", ");
	// 		printf("%lld",fact);
	// 	}
	// }
	// printf("};\n");
	// printf("ll multfact[2000]={%d", vt[0]);
	// vt.erase(vt.begin());
	// for(int x : vt){
	// 	printf(",%d",x);
	// }
	// printf("};");
	// int fact = 1;
	// int mult = 1;
	// for(int i = 1; i<=lim; i++){
	// 	fact = 1ll * fact * i % mod;
	// 	mult = 1ll * mult * fact % mod;
	// }
	// cout << fact << endl;
	// cout << mult << endl;
	int t;
	scanf("%d", &t);
	while(t--){
		int l, r;
		scanf("%d %d", &l, &r);
		ll mult = 1;

		// for(int i = l; i<=r; i++)
		// {
		// 	mult = mult * bigmod(i, i+1) % mod;
		// }
		// cout << mult << " ";
		cout << fun(r) * bigmod(fun(l-1), mod-2) % mod << endl;
	}
	return 0;
}

Notice that for any two non-negative integers $$$a$$$ and $$$b$$$, $$$a$$$ & $$$b$$$ $$$<$$$ $$$a$$$ and $$$a$$$ & $$$b$$$ $$$<$$$ $$$b$$$.

So the minimum value of all possible subset AND is the bitwise AND of all of the elements of the array. So just check if it less than $$$k$$$ or not.

#include<bits/stdc++.h>
using namespace std;



int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,k,x;
        cin >> n >> k ;
        int an;
        cin >> an;
        n--;
        while(n--)
        {
            cin >> x;
            an&=x;
        }
        if(an<k) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

Dp state for our solution is ( position , $$$c_0$$$ , $$$c_1$$$), here $$$c_0,c_1$$$ indicates the remaining count of zeroes and ones in the second string which we can still use to form a subsequence of the first string. For counting only the distinct permutations, from every position we go to the position of next zero and one and return 1 when we reach the state where $$$c_0=0$$$ and $$$c_1=0$$$.

Here the length of the strings can be up to $$$700$$$. Solutions with $$$O(N^3)$$$ memory won’t pass. So, we need to reduce a state. We can do bottom-up and get rid of the state position. The only difficulty here is that, in our usual bottom-up solutions, for any position, we need the dp values from the previous position. But here we are jumping from current position to the position with next zero or one(not necessarily position$$$+1$$$). For that, we can save dp values for the last one and last zero before current position and use those values to calculate dp for current position.

#include<bits/stdc++.h>
using namespace std;

#define N 710
#define mod 1000000007

int dp[2][N][N];
int all[2][N][N];
int pos[2],pre[2][N];
int cnt[2];

int main()
{
    
    string s1,s2;
    cin >> s1 >> s2;
    pos[0]=pos[1]=-1;
    for(int i=0; i<s1.size(); i++)
    {
        pre[0][i]=pos[0];
        pre[1][i]=pos[1];
        pos[s1[i]-'0']=i;
    }
    for(int i=0; i<s2.size(); i++) cnt[s2[i]-'0']++;
    int ans=0;
    for(int p=0; p<s1.size(); p++)
    {
        int nw=s1[p]-'0';
        if(nw==0)
        {
            if(pre[nw][p]==-1)
            {
                dp[0][1][0]=1;
                all[0][1][0]=1;
                for(int i=1; i<=cnt[1]; i++)
                {
                    dp[0][1][i]=all[1][0][i];
                    all[0][1][i]=all[1][0][i];
                }
            }
            else
            {
                for(int i=cnt[0]; i>=0; i--)
                {
                    for(int j=cnt[1]; j>=0; j--)
                    {
                        if(i>0) dp[0][i][j]=dp[0][i-1][j];
                        else dp[0][i][j]=0;
                        if(i>0) dp[0][i][j]+=all[1][i-1][j];
                        dp[0][i][j]%=mod;
                        all[0][i][j]+=dp[0][i][j];
                        all[0][i][j]%=mod;
                    }
                }
            }
            memset(all[1],0,sizeof (all[1]));
            ans+=dp[0][cnt[0]][cnt[1]];
            ans%=mod;

        }
        else
        {
            if(pre[nw][p]==-1)
            {
                dp[1][0][1]=1;
                all[1][0][1]=1;
                for(int i=1; i<=cnt[0]; i++)
                {
                    dp[1][i][1]=all[0][i][0];
                    all[1][i][1]=all[0][i][0];
                }
            }
            else
            {
                for(int i=cnt[0]; i>=0; i--)
                {
                    for(int j=cnt[1]; j>=0; j--)
                    {
                        if(j>0) dp[1][i][j]=dp[1][i][j-1];
                        else dp[1][i][j]=0;
                        if(j>0) dp[1][i][j]+=all[0][i][j-1];
                        dp[1][i][j]%=mod;
                        all[1][i][j]+=dp[1][i][j];
                        all[1][i][j]%=mod;
                    }
                }
            }
            memset(all[0],0,sizeof (all[0]));
            ans+=dp[1][cnt[0]][cnt[1]];
            ans%=mod;
        }
    }
    cout<<ans<<endl;


}

So we need to find the sum of the cost of all possible spanning trees in a complete graph where the weight of an edge from $$$i$$$ to $$$j$$$ is $$$i*j$$$.

Let's find the contribution of an edge $$$(i \rightarrow j)$$$ to the final answer. In how many spanning trees does this edge exist? Let's go deeper in Cayley's Formula. If there are $$$k$$$ connected components in a graph having $$$n$$$ nodes each having size $$$s_1, s_2,...,s_k$$$ then the number of ways to connect them is

Refer to this for proof.

So if we connect edge $$$i \rightarrow j$$$ and disconnect every other edge then the number of ways to connect every component is the same as the number of spanning trees in which this edge is included. And it equals to $$$2*n^{n-3}$$$. As this is a complete graph this value is the same for every other edge.

Let $$$C \; =$$$ sum of the costs of all edges in the graph. So our final answer is $$$2*n^{n-3}*C$$$.

Here $$$2*C \; =$$$ square of the sum of natural numbers up to $$$n$$$ — the sum of squared natural numbers up to $$$n$$$.

So we can solve the problem in $$$O(log \; n)$$$.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 1000000007

ll bm(ll b,ll p)
{
    ll ret=1;
    b=b%mod;p=p%(mod-1);
    while(p)
    {
        if(p&1) ret=(ret*b)%mod;
        p/=2;
        b=(b*b)%mod;
    }
    return ret;
}

int main()
{
    int t;
    ll n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        if(n==2)
        {
            cout<<"2"<<endl;
            continue;
        }
        ll sum=n%mod*((n+1)%mod)%mod;
        sum=sum*bm(2,mod-2)%mod;

        sum=sum%mod*sum%mod;

        ll tmp=n%mod*((n+1)%mod)%mod*((2LL*n+1)%mod)%mod;
        tmp=tmp%mod*bm(6,mod-2)%mod;

        ll ans=(sum-tmp+mod)%mod;
        ans=ans%mod*bm(2,mod-2)%mod;
        ans=ans%mod*2LL%mod*bm(n,n-3)%mod;
        cout<<ans<<endl;
    }
}

#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
using namespace std;
int ara[mx*10];
ll bigmod(ll a, ll p){
	ll ret = 1;
	while(p){
		if(p&1) ret = ret * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return ret;
}
void myassert(int x, int l, int r){
	assert(x <= r);
	assert(l <= x);
}
int main()
{
	// freopen("in12.txt", "r", stdin);
	map<int, int> mp;
	int sz = 0;
	int a;
	scanf("%d", &sz);
	for(int i = 0; i<sz; i++)
		scanf("%d", &ara[i]);
	assert(sz <= 1000000);
	assert(1 <= sz);
	int n, m;
	scanf("%d %d", &n, &m);
	myassert(n, 1, 1000000000);
	myassert(m, 1, 1000000000);
	for(int i = 0; i<sz; i++){
		mp[ara[i]%m]++;
	}
	// cout << mp.size() << endl;
	ll ans = 0;
	for(auto p : mp){
		if(p.first == ((m-p.first)%m)) ans = (ans + bigmod(p.second, n)) % mod;
		else{
			if(mp.find((m-p.first)%m) == mp.end()) continue;
			ll nw = mp[(m-p.first)%m];
			ll nwans = bigmod(p.second, n/2) * bigmod(nw, n-(n/2)) % mod;
			ans = (ans + nwans) % mod;
		} 
	}
	printf("%lld\n", ans);
	return 0;
}

TBA

~~~~~

~~~~~