[problem:1245A]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int gcd(int a, int b)↵
{↵
while (b)↵
{↵
a %= b;↵
swap(a, b);↵
}↵
↵
return a;↵
}↵
↵
int main()↵
{↵
int t;↵
for (cin >> t; t--;)↵
↵
{↵
int a, b;↵
cin >> a >> b;↵
↵
if (gcd(a, b) == 1)↵
cout << "Finite" << '\n';↵
else↵
cout << "Infinite" << '\n';↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1245B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int q;↵
for (cin >> q; q--;)↵
{↵
int n;↵
cin >> n;↵
int a, b, c;↵
cin >> a >> b >> c;↵
string s;↵
cin >> s;↵
↵
vector<int> count(26);↵
for (char x : s)↵
count[x - 'A']++;↵
↵
int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);↵
↵
if (2 * wins < n)↵
{↵
cout << "NO" << '\n';continue;↵
}↵
↵
cout << "YES" << '\n';↵
string t;↵
for (int i = 0; i != n; ++i)↵
{↵
if (s[i] == 'S' && a)↵
{↵
t += 'R';↵
a--;↵
}↵
else if (s[i] == 'R' && b)↵
{↵
t += 'P';↵
b--;↵
}↵
else if (s[i] == 'P' && c)↵
{↵
t += 'S';↵
c--;↵
}↵
else↵
t += '_';↵
}↵
for (int i = 0; i != n; ++i)↵
{↵
if (t[i] != '_')↵
continue;↵
↵
if (a)↵
{↵
t[i] = 'R';↵
a--;↵
}↵
else if (b)↵
{↵
t[i] = 'P';↵
b--;↵
}↵
else↵
{↵
t[i] = 'S';↵
c--;↵
}↵
}↵
cout << t << '\n';↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1245C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵
↵
const int MOD = 1000000007;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
string s;↵
cin >> s;↵
↵
for (char x : s)↵
{↵
if (x == 'w' || x == 'm')↵
{↵
cout << 0 << '\n';↵
return 0;↵
}↵
}↵
↵
int n = s.size();↵
vector<int> dp(n + 1);↵
dp[0] = 1;↵
dp[1] = 1;↵
for (int i = 2; i <= n; ++i)↵
{↵
dp[i] = dp[i - 1];↵
if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n'))↵
dp[i] = (dp[i] + dp[i - 2]) % MOD;↵
}↵
↵
cout << dp[n] << '\n';↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Arpa)">↵
↵
~~~~~↵
// In the name of Allah.↵
// We're nothing and you're everything.↵
// Ya Ali!↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
const int maxn = 1e5 + 14, mod = 1e9 + 7;↵
↵
int n, fib[maxn];↵
↵
int main(){↵
ios::sync_with_stdio(0), cin.tie(0);↵
fib[0] = fib[1] = 1;↵
for(int i = 2; i < maxn; i++)↵
fib[i] = (fib[i - 1] + fib[i - 2]) % mod;↵
string s;↵
cin >> s;↵
n = s.size();↵
if(s.find('m') != -1 || s.find('w') != -1)↵
return cout << "0\n", 0;↵
int ans = 1;↵
for(int i = 0, j = 0; i < n; i = j){↵
while(j < n && s[j] == s[i])↵
j++;↵
if(s[i] == 'n' || s[i] == 'u')↵
ans = (ll) ans * fib[j - i] % mod;↵
}↵
cout << ans << '\n';↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1245D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int n;↵
cin >> n;↵
pair<int, int> pos[n];↵
for (int i = 0; i != n; ++i)↵
cin >> pos[i].first >> pos[i].second;↵
int c[n];↵
for (int i = 0; i != n; ++i)↵
cin >> c[i];↵
int k[n];↵
for (int i = 0; i != n; ++i)↵
cin >> k[i];↵
↵
long long ans = 0;↵
vector<int> power_plants;↵
vector<pair<int, int>> connections;↵
↵
vector<bool> done(n);↵
vector<int> parent(n, -1);↵
for (int _n = n; _n--;)↵
{↵
int mi = 2000000000;↵
int u = -1;↵
for (int i = 0; i != n; ++i)↵
{↵
if (done[i])↵
continue;↵
↵
if (c[i] < mi)↵
{↵
mi = c[i];↵
u = i;↵
}↵
}↵
↵
ans += mi;↵
done[u] = 1;↵
if (parent[u] == -1)↵
power_plants.push_back(u);↵
else↵
connections.push_back(make_pair(min(parent[u], u), max(parent[u], u)));↵
↵
for (int i = 0; i != n; ++i)↵
if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i])↵
{↵
c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second));↵
parent[i] = u;↵
}↵
}↵
↵
cout << ans << '\n';↵
cout << power_plants.size() << '\n';↵
sort(power_plants.begin(), power_plants.end());↵
for (int x : power_plants)↵
cout << x + 1 << ' ';↵
cout << '\n';↵
cout << connections.size() << '\n';↵
for (pair<int, int> x : connections)↵
cout << x.first + 1 << ' ' << x.second + 1 << '\n';↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (PikMike)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for(int i = 0; i < int(n); i++) ↵
↵
int main(){↵
int n;↵
scanf("%d", &n);↵
vector<int> x(n), y(n);↵
forn(i, n)↵
scanf("%d%d", &x[i], &y[i]);↵
vector<int> c(n), k(n);↵
forn(i, n)↵
scanf("%d", &c[i]);↵
forn(i, n)↵
scanf("%d", &k[i]);↵
↵
++n;↵
vector<int> p(n, -1);↵
vector<int> d(n, int(1e9));↵
vector<bool> used(n);↵
↵
forn(i, n - 1){↵
d[i] = c[i];↵
p[i] = n - 1;↵
}↵
used[n - 1] = true;↵
↵
long long ans = 0;↵
vector<int> vv;↵
vector<pair<int, int>> ee;↵
↵
forn(_, n - 1){↵
int v = -1;↵
forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i]))↵
v = i;↵
↵
if (p[v] == n - 1)↵
vv.push_back(v + 1);↵
else↵
ee.push_back(make_pair(v + 1, p[v] + 1));↵
ans += d[v];↵
↵
used[v] = true;↵
forn(i, n) if (!used[i]){↵
long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i]));↵
if (dist < d[i]){↵
d[i] = dist;↵
p[i] = v;↵
}↵
}↵
}↵
↵
printf("%lld\n", ans);↵
printf("%d\n", int(vv.size()));↵
for (auto it : vv)↵
printf("%d ", it);↵
puts("");↵
printf("%d\n", int(ee.size()));↵
for (auto it : ee)↵
printf("%d %d\n", it.first, it.second);↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1245E]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int grid[10][10];↵
for (int i = 0; i != 10; ++i)↵
for (int j = 0; j != 10; ++j)↵
cin >> grid[i][j];↵
↵
int flat[10][10];↵
for (int i = 0; i != 10; ++i)↵
for (int j = 0; j != 10; ++j)↵
flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);↵
↵
int d = 1;↵
int x = 9;↵
int y = 0;↵
int arr[100];↵
for (int i = 0; i != 100; ++i)↵
{↵
arr[i] = flat[x - grid[x][y]][y];↵
↵
if (y + d == -1 || y + d == 10)↵
{↵
d *= -1;↵
x--;↵
}↵
else↵
y += d;↵
}↵
↵
double dp[100];↵
dp[99] = 0;↵
for (int i = 98; i >= 0; --i)↵
{↵
dp[i] = 1;↵
↵
int c = 6;↵
for (int r = 1; r <= 6; ++r)↵
{↵
if (i + r >= 100)↵
continue;↵
dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6;↵
c--;↵
}↵
↵
dp[i] = 6 * dp[i] / (6 - c);↵
}↵
↵
cout << setprecision(10) << fixed << dp[0] << '\n';↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1245F]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int f(int a, int b)↵
{↵
int ret = 0;↵
int zeroes = 0;↵
↵
for (int i = 1; i <= b; i <<= 1)↵
{↵
if (b & i)↵
{↵
b ^= i;↵
↵
if (!(a & b))↵
ret += 1 << zeroes;↵
}↵
↵
if (!(a & i))↵
zeroes++;↵
}↵
↵
return ret;↵
}↵
↵
long long rec(int a, int b)↵
{↵
if (a == b)↵
return 0;↵
if (a == 0)↵
return 2 * b - 1 + rec(1, b);↵
↵
long long ret = 0;↵
if (a & 1)↵
{↵
ret += 2 * (f(a, b) - f(a, a));↵
a++;↵
}↵
if (b & 1)↵
{↵
ret += 2 * (f(b - 1, b) - f(b - 1, a));↵
b--;↵
}↵
↵
return ret + 3 * rec(a / 2, b / 2);↵
}↵
↵
int main()↵
{↵
int t;↵
for (cin >> t; t--;)↵
{↵
int a, b;↵
cin >> a >> b;↵
cout << rec(a, b + 1) << '\n';↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int gcd(int a, int b)↵
{↵
while (b)↵
{↵
a %= b;↵
swap(a, b);↵
}↵
↵
return a;↵
}↵
↵
int main()↵
{↵
int t;↵
for (cin >> t; t--;)↵
↵
{↵
int a, b;↵
cin >> a >> b;↵
↵
if (gcd(a, b) == 1)↵
cout << "Finite" << '\n';↵
else↵
cout << "Infinite" << '\n';↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1245B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int q;↵
for (cin >> q; q--;)↵
{↵
int n;↵
cin >> n;↵
int a, b, c;↵
cin >> a >> b >> c;↵
string s;↵
cin >> s;↵
↵
vector<int> count(26);↵
for (char x : s)↵
count[x - 'A']++;↵
↵
int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);↵
↵
if (2 * wins < n)↵
{↵
cout << "NO" << '\n';continue;↵
}↵
↵
cout << "YES" << '\n';↵
string t;↵
for (int i = 0; i != n; ++i)↵
{↵
if (s[i] == 'S' && a)↵
{↵
t += 'R';↵
a--;↵
}↵
else if (s[i] == 'R' && b)↵
{↵
t += 'P';↵
b--;↵
}↵
else if (s[i] == 'P' && c)↵
{↵
t += 'S';↵
c--;↵
}↵
else↵
t += '_';↵
}↵
for (int i = 0; i != n; ++i)↵
{↵
if (t[i] != '_')↵
continue;↵
↵
if (a)↵
{↵
t[i] = 'R';↵
a--;↵
}↵
else if (b)↵
{↵
t[i] = 'P';↵
b--;↵
}↵
else↵
{↵
t[i] = 'S';↵
c--;↵
}↵
}↵
cout << t << '\n';↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1245C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵
↵
const int MOD = 1000000007;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
string s;↵
cin >> s;↵
↵
for (char x : s)↵
{↵
if (x == 'w' || x == 'm')↵
{↵
cout << 0 << '\n';↵
return 0;↵
}↵
}↵
↵
int n = s.size();↵
vector<int> dp(n + 1);↵
dp[0] = 1;↵
dp[1] = 1;↵
for (int i = 2; i <= n; ++i)↵
{↵
dp[i] = dp[i - 1];↵
if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n'))↵
dp[i] = (dp[i] + dp[i - 2]) % MOD;↵
}↵
↵
cout << dp[n] << '\n';↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Arpa)">↵
↵
~~~~~↵
// In the name of Allah.↵
// We're nothing and you're everything.↵
// Ya Ali!↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
↵
const int maxn = 1e5 + 14, mod = 1e9 + 7;↵
↵
int n, fib[maxn];↵
↵
int main(){↵
ios::sync_with_stdio(0), cin.tie(0);↵
fib[0] = fib[1] = 1;↵
for(int i = 2; i < maxn; i++)↵
fib[i] = (fib[i - 1] + fib[i - 2]) % mod;↵
string s;↵
cin >> s;↵
n = s.size();↵
if(s.find('m') != -1 || s.find('w') != -1)↵
return cout << "0\n", 0;↵
int ans = 1;↵
for(int i = 0, j = 0; i < n; i = j){↵
while(j < n && s[j] == s[i])↵
j++;↵
if(s[i] == 'n' || s[i] == 'u')↵
ans = (ll) ans * fib[j - i] % mod;↵
}↵
cout << ans << '\n';↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1245D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int n;↵
cin >> n;↵
pair<int, int> pos[n];↵
for (int i = 0; i != n; ++i)↵
cin >> pos[i].first >> pos[i].second;↵
int c[n];↵
for (int i = 0; i != n; ++i)↵
cin >> c[i];↵
int k[n];↵
for (int i = 0; i != n; ++i)↵
cin >> k[i];↵
↵
long long ans = 0;↵
vector<int> power_plants;↵
vector<pair<int, int>> connections;↵
↵
vector<bool> done(n);↵
vector<int> parent(n, -1);↵
for (int _n = n; _n--;)↵
{↵
int mi = 2000000000;↵
int u = -1;↵
for (int i = 0; i != n; ++i)↵
{↵
if (done[i])↵
continue;↵
↵
if (c[i] < mi)↵
{↵
mi = c[i];↵
u = i;↵
}↵
}↵
↵
ans += mi;↵
done[u] = 1;↵
if (parent[u] == -1)↵
power_plants.push_back(u);↵
else↵
connections.push_back(make_pair(min(parent[u], u), max(parent[u], u)));↵
↵
for (int i = 0; i != n; ++i)↵
if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i])↵
{↵
c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second));↵
parent[i] = u;↵
}↵
}↵
↵
cout << ans << '\n';↵
cout << power_plants.size() << '\n';↵
sort(power_plants.begin(), power_plants.end());↵
for (int x : power_plants)↵
cout << x + 1 << ' ';↵
cout << '\n';↵
cout << connections.size() << '\n';↵
for (pair<int, int> x : connections)↵
cout << x.first + 1 << ' ' << x.second + 1 << '\n';↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (PikMike)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define forn(i, n) for(int i = 0; i < int(n); i++) ↵
↵
int main(){↵
int n;↵
scanf("%d", &n);↵
vector<int> x(n), y(n);↵
forn(i, n)↵
scanf("%d%d", &x[i], &y[i]);↵
vector<int> c(n), k(n);↵
forn(i, n)↵
scanf("%d", &c[i]);↵
forn(i, n)↵
scanf("%d", &k[i]);↵
↵
++n;↵
vector<int> p(n, -1);↵
vector<int> d(n, int(1e9));↵
vector<bool> used(n);↵
↵
forn(i, n - 1){↵
d[i] = c[i];↵
p[i] = n - 1;↵
}↵
used[n - 1] = true;↵
↵
long long ans = 0;↵
vector<int> vv;↵
vector<pair<int, int>> ee;↵
↵
forn(_, n - 1){↵
int v = -1;↵
forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i]))↵
v = i;↵
↵
if (p[v] == n - 1)↵
vv.push_back(v + 1);↵
else↵
ee.push_back(make_pair(v + 1, p[v] + 1));↵
ans += d[v];↵
↵
used[v] = true;↵
forn(i, n) if (!used[i]){↵
long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i]));↵
if (dist < d[i]){↵
d[i] = dist;↵
p[i] = v;↵
}↵
}↵
}↵
↵
printf("%lld\n", ans);↵
printf("%d\n", int(vv.size()));↵
for (auto it : vv)↵
printf("%d ", it);↵
puts("");↵
printf("%d\n", int(ee.size()));↵
for (auto it : ee)↵
printf("%d %d\n", it.first, it.second);↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1245E]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int grid[10][10];↵
for (int i = 0; i != 10; ++i)↵
for (int j = 0; j != 10; ++j)↵
cin >> grid[i][j];↵
↵
int flat[10][10];↵
for (int i = 0; i != 10; ++i)↵
for (int j = 0; j != 10; ++j)↵
flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);↵
↵
int d = 1;↵
int x = 9;↵
int y = 0;↵
int arr[100];↵
for (int i = 0; i != 100; ++i)↵
{↵
arr[i] = flat[x - grid[x][y]][y];↵
↵
if (y + d == -1 || y + d == 10)↵
{↵
d *= -1;↵
x--;↵
}↵
else↵
y += d;↵
}↵
↵
double dp[100];↵
dp[99] = 0;↵
for (int i = 98; i >= 0; --i)↵
{↵
dp[i] = 1;↵
↵
int c = 6;↵
for (int r = 1; r <= 6; ++r)↵
{↵
if (i + r >= 100)↵
continue;↵
dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6;↵
c--;↵
}↵
↵
dp[i] = 6 * dp[i] / (6 - c);↵
}↵
↵
cout << setprecision(10) << fixed << dp[0] << '\n';↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1245F]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1245F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int f(int a, int b)↵
{↵
int ret = 0;↵
int zeroes = 0;↵
↵
for (int i = 1; i <= b; i <<= 1)↵
{↵
if (b & i)↵
{↵
b ^= i;↵
↵
if (!(a & b))↵
ret += 1 << zeroes;↵
}↵
↵
if (!(a & i))↵
zeroes++;↵
}↵
↵
return ret;↵
}↵
↵
long long rec(int a, int b)↵
{↵
if (a == b)↵
return 0;↵
if (a == 0)↵
return 2 * b - 1 + rec(1, b);↵
↵
long long ret = 0;↵
if (a & 1)↵
{↵
ret += 2 * (f(a, b) - f(a, a));↵
a++;↵
}↵
if (b & 1)↵
{↵
ret += 2 * (f(b - 1, b) - f(b - 1, a));↵
b--;↵
}↵
↵
return ret + 3 * rec(a / 2, b / 2);↵
}↵
↵
int main()↵
{↵
int t;↵
for (cin >> t; t--;)↵
{↵
int a, b;↵
cin >> a >> b;↵
cout << rec(a, b + 1) << '\n';↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
