A. Good ol' Numbers Coloring
time limit per test1 second memory limit per test256 megabytes
Consider the set of all nonnegative integers: \({0, 1, 2, \dots}\). Given two integers a and b \((1 \le a, b \le 10^4)\). We paint all the numbers in increasing number first we paint 0, then we paint 1, then 2 and so on.
Each number is painted white or black. We paint a number i according to the following rules:
- if i = 0, it is colored white;
- if \(i \ge a\) and i - a is colored white, i is also colored white;
- if \(i \ge b\) and i - b is colored white, i is also colored white;
- if i is still not colored white, it is colored black.
In this way, each nonnegative integer gets one of two colors.
For example, if a=3, b=5, then the colors of the numbers (in the order from 0) are: white (0), black (1), black (2), white (3), black (4), white (5), white (6), black (7), white (8), white (9), ...
Note that:
- It is possible that there are infinitely many nonnegative integers colored black. For example, if a = 10 and b = 10, then only 0, 10, 20, 30 and any other nonnegative integers that end in 0 when written in base 10 are white. The other integers are colored black.
- It is also possible that there are only finitely many nonnegative integers colored black. For example, when a = 1 and b = 10, then there is no nonnegative integer colored black at all.
Your task is to determine whether or not the number of nonnegative integers colored black is infinite.
If there are infinitely many nonnegative integers colored black, simply print a line containing "Infinite" (without the quotes). Otherwise, print "Finite" (without the quotes).
Input
The first line of input contains a single integer t \((1 \le t \le 100)\) — the number of test cases in the input. Then t lines follow, each line contains two space-separated integers a and b \((1 \le a, b \le 10^4)\).
Output
For each test case, print one line containing either "Infinite" or "Finite" (without the quotes). Output is case-insensitive (i.e. "infinite", "inFiNite" or "finiTE" are all valid answers).
Exampleinput
4 10 10 1 10 6 9 7 3
output
Infinite Finite Infinite Finite
签到，互质即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void solve(){
int a,b;cin>>a>>b;
if(gcd(a,b)==1) puts("finite");
else puts("inFinite");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Restricted RPS
time limit per test1 second memory limit per test256 megabytes
Let n be a positive integer. Let a, b, c be nonnegative integers such that a + b + c = n.
Alice and Bob are gonna play rock-paper-scissors n times. Alice knows the sequences of hands that Bob will play. However, Alice has to play rock a times, paper b times, and scissors c times.
Alice wins if she beats Bob in at least \(\lceil \frac{n}{2} \rceil (\frac{n}{2}\) rounded up to the nearest integer) hands, otherwise Alice loses.
Note that in rock-paper-scissors:
- rock beats scissors;
- paper beats rock;
- scissors beat paper.
The task is, given the sequence of hands that Bob will play, and the numbers a, b, c, determine whether or not Alice can win. And if so, find any possible sequence of hands that Alice can use to win.
If there are multiple answers, print any of them.Input
The first line contains a single integer t \((1 \le t \le 100)\) — the number of test cases.
Then, t testcases follow, each consisting of three lines:
- The first line contains a single integer n \((1 \le n \le 100)\).
- The second line contains three integers, a, b, c \((0 \le a, b, c \le n)\). It is guaranteed that a + b + c = n.
- The third line contains a string s of length n. s is made up of only 'R', 'P', and 'S'. The i-th character is 'R' if for his i-th Bob plays rock, 'P' if paper, and 'S' if scissors.
Output
For each testcase:
- If Alice cannot win, print "NO" (without the quotes).
- Otherwise, print "YES" (without the quotes). Also, print a string t of length n made up of only 'R', 'P', and 'S' — a sequence of hands that Alice can use to win. t must contain exactly a 'R's, b 'P's, and c 'S's.
- If there are multiple answers, print any of them.
The "YES" / "NO" part of the output is case-insensitive (i.e. "yEs", "no" or "YEs" are all valid answers). Note that 'R', 'P' and 'S' are case-sensitive.
Exampleinput
2 3 1 1 1 RPS 3 3 0 0 RPS
output
YES PSR NO
Note
In the first testcase, in the first hand, Alice plays paper and Bob plays rock, so Alice beats Bob. In the second hand, Alice plays scissors and Bob plays paper, so Alice beats Bob. In the third hand, Alice plays rock and Bob plays scissors, so Alice beats Bob. Alice beat Bob 3 times, and \(3 \ge \lceil \frac{3}{2} \rceil = 2\), so Alice wins.
In the second testcase, the only sequence of hands that Alice can play is "RRR". Alice beats Bob only in the last hand, so Alice can't win. \(1 < \lceil \frac{3}{2} \rceil = 2\).
签到，模拟即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,a,b,c,pos,cnt;
char s[maxn],ans[110];
void solve(){
pos=0;cnt=0;
scanf("%d",&n);
cin>>a>>b>>c;
scanf("%s",s+1);
int aa=0,bb=0,cc=0;
rep(i,1,n){
if(s[i]=='R') bb++;
if(s[i]=='P') cc++;
if(s[i]=='S') aa++;
ans[i]='*';
}
if(min(a,aa)+min(b,bb)+min(c,cc)>=(n+1)/2){
puts("YES");
rep(i,1,n){
if(s[i]=='R'&&b) b--,ans[i]='P';
if(s[i]=='P'&&c) c--,ans[i]='S';
if(s[i]=='S'&&a) a--,ans[i]='R';
}
rep(i,1,n){
if(ans[i]!='*') printf("%c",ans[i]);
else if(a) a--,printf("R");
else if(b) b--,printf("P");
else c--,printf("S");
}
puts("");
}
else puts("NO");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. Constanze's Machine
time limit per test1 second memory limit per test256 megabytes
Constanze is the smartest girl in her village but she has bad eyesight.
One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce 'c', 'o', 'd', and 'e' in that order, then the machine will inscribe "code" onto the paper. Thanks to this machine, she can finally write messages without using her glasses.
However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce 'w', it will inscribe "uu" instead of "w", and if you pronounce 'm', it will inscribe "nn" instead of "m"! Since Constanze had bad eyesight, she was not able to realize what Akko did.
The rest of the letters behave the same as before: if you pronounce any letter besides 'w' and 'm', the machine will just inscribe it onto a piece of paper.
The next day, I received a letter in my mailbox. I can't understand it so I think it's either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze's machine would have turned into the message I got and see if anything makes sense.
But I need to know how much paper I will need, and that's why I'm asking you for help. Tell me the number of strings that Constanze's machine would've turned into the message I got.
But since this number can be quite large, tell me instead its remainder when divided by \(10^9+7\).
If there are no strings that Constanze's machine would've turned into the message I got, then print 0.
Input
Input consists of a single line containing a string s \((1 \leq |s| \leq 10^5)\) — the received message. s contains only lowercase Latin letters.
Output
Print a single integer — the number of strings that Constanze's machine would've turned into the message s, modulo \(10^9+7\).
Examplesinput
ouuokarinn
output
4
input
banana
output
1
input
nnn
output
3
input
amanda
output
0
Note
For the first example, the candidate strings are the following: "ouuokarinn", "ouuokarim", "owokarim", and "owokarinn".
For the second example, there is only one: "banana".
For the third example, the candidate strings are the following: "nm", "mn" and "nnn".
For the last example, there are no candidate strings that the machine can turn into "amanda", since the machine won't inscribe 'm'.
斐波那契乘一下就好啦
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
ll f[maxn];
int ans=1;
char s[maxn];
int main(){
f[2]=2;f[3]=3;
scanf("%s",s+1);
int n=strlen(s+1),cnt=1;
rep(i,4,n) f[i]=(f[i-1]+f[i-2])%mod;
rep(i,1,n) if(s[i]=='m'||s[i]=='w') return puts("0"),0;
char pre=s[1];s[n+1]='*';n++;
rep(i,2,n){
if(s[i]==pre) cnt++;
else{
if((pre=='u'||pre=='n')&&cnt>1) ans=ans*f[cnt]%mod;
cnt=1;
}
pre=s[i];
}
printf("%d\n",ans);
}
D. Shichikuji and Power Grid
time limit per test2 seconds memory limit per test256 megabytes
Shichikuji is the new resident deity of the South Black Snail Temple. Her first job is as follows:
There are n new cities located in Prefecture X. Cities are numbered from 1 to n. City i is located \(x_i\) km North of the shrine and \(y_i\) km East of the shrine. It is possible that \((x_i, y_i) = (x_j, y_j)\) even when \(i \ne j\).
Shichikuji must provide electricity to each city either by building a power station in that city, or by making a connection between that city and another one that already has electricity. So the City has electricity if it has a power station in it or it is connected to a City which has electricity by a direct connection or via a chain of connections.
- Building a power station in City i will cost \(c_i\) yen;
- Making a connection between City i and City j will cost \(k_i + k_j\) yen per km of wire used for the connection. However, wires can only go the cardinal directions (North, South, East, West). Wires can cross each other. Each wire must have both of its endpoints in some cities. If City i and City j are connected by a wire, the wire will go through any shortest path from City i to City j. Thus, the length of the wire if City i and City j are connected is \(|x_i - x_j| + |y_i - y_j|\) km.
Shichikuji wants to do this job spending as little money as possible, since according to her, there isn't really anything else in the world other than money. However, she died when she was only in fifth grade so she is not smart enough for this. And thus, the new resident deity asks for your help.
And so, you have to provide Shichikuji with the following information: minimum amount of yen needed to provide electricity to all cities, the cities in which power stations will be built, and the connections to be made.
If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.
Input
First line of input contains a single integer n \((1 \leq n \leq 2000)\) — the number of cities.
Then, n lines follow. The i-th line contains two space-separated integers \(x_i (1 \leq x_i \leq 10^6)\) and\( y_i (1 \leq y_i \leq 10^6)\) — the coordinates of the i-th city.
The next line contains n space-separated integers \(c_1, c_2, \dots, c_n (1 \leq c_i \leq 10^9)\) — the cost of building a power station in the i-th city.
The last line contains n space-separated integers \(k_1, k_2, \dots, k_n (1 \leq k_i \leq 10^9)\).
Output
In the first line print a single integer, denoting the minimum amount of yen needed.
Then, print an integer v — the number of power stations to be built.
Next, print v space-separated integers, denoting the indices of cities in which a power station will be built. Each number should be from 1 to n and all numbers should be pairwise distinct. You can print the numbers in arbitrary order.
After that, print an integer e — the number of connections to be made.
Finally, print e pairs of integers a and b \((1 \le a, b \le n, a \ne b)\), denoting that a connection between City a and City b will be made. Each unordered pair of cities should be included at most once (for each (a, b) there should be no more (a, b) or (b, a) pairs). You can print the pairs in arbitrary order.
If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.
Examplesinput
3 2 3 1 1 3 2 3 2 3 3 2 3
output
8 3 1 2 3 0
input
3 2 1 1 2 3 3 23 2 23 3 2 3
output
27 1 2 2 1 2 2 3
Note
For the answers given in the samples, refer to the following diagrams (cities with power stations are colored green, other cities are colored blue, and wires are colored red):
For the first example, the cost of building power stations in all cities is 3 + 2 + 3 = 8. It can be shown that no configuration costs less than 8 yen.
For the second example, the cost of building a power station in City 2 is 2. The cost of connecting City 1 and City 2 is \(2 \cdot (3 + 2) = 10\). The cost of connecting City 2 and City 3 is \(3 \cdot (2 + 3) = 15\). Thus the total cost is 2 + 10 + 15 = 27. It can be shown that no configuration costs less than 27 yen.
最小生成树裸题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const ll maxn=(ll)1e6+100;
const ll mod=(ll)1e9+7;
ll n,x[maxn],y[maxn],c[maxn],k[maxn],pre[maxn];
ll find(ll x){return pre[x]==x?x:pre[x]=find(pre[x]);}
struct edge{
ll u,v,w;
bool operator<(edge b)const{return w<b.w;}
}e[maxn<<2];
ll fun(ll i,ll j){return (k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]));}
int main(){
scanf("%lld",&n);
rep(i,1,n) pre[i]=i;
rep(i,1,n) scanf("%lld%lld",&x[i],&y[i]);
rep(i,1,n) scanf("%lld",&c[i]);
rep(i,1,n) scanf("%lld",&k[i]);
ll pos=0,ans=0;
vector<ll> vec,eg;
rep(i,1,n) e[++pos]={0,i,c[i]};
rep(i,1,n) rep(j,i+1,n) e[++pos]={i,j,fun(i,j)};
sort(e+1,e+1+pos);
rep(i,1,pos){
ll u=find(e[i].u),v=find(e[i].v);
if(u!=v){
ans+=e[i].w;
if(e[i].u==0||e[i].v==0) vec.pb(max(e[i].u,e[i].v));
else eg.pb(i);
pre[u]=v;
}
}
printf("%lld\n%d\n",ans,(int)vec.size());
for(auto u:vec) printf("%lld ",u);
printf("\n%d\n",(int)eg.size());
for(auto u:eg) printf("%lld %lld\n",e[u].u,e[u].v);
}
E. Hyakugoku and Ladders
time limit per test1 second memory limit per test256 megabytes
Hyakugoku has just retired from being the resident deity of the South Black Snail Temple in order to pursue her dream of becoming a cartoonist. She spent six months in that temple just playing "Cat's Cradle" so now she wants to try a different game — "Snakes and Ladders". Unfortunately, she already killed all the snakes, so there are only ladders left now.
The game is played on a \(10 \times 10\) board as follows:
- At the beginning of the game, the player is at the bottom left square.
- The objective of the game is for the player to reach the Goal (the top left square) by following the path and climbing vertical ladders. Once the player reaches the Goal, the game ends.
- The path is as follows: if a square is not the end of its row, it leads to the square next to it along the direction of its row; if a square is the end of its row, it leads to the square above it. The direction of a row is determined as follows: the direction of the bottom row is to the right; the direction of any other row is opposite the direction of the row below it. See Notes section for visualization of path.
- During each turn, the player rolls a standard six-sided dice. Suppose that the number shown on the dice is r. If the Goal is less than r squares away on the path, the player doesn't move (but the turn is performed). Otherwise, the player advances exactly r squares along the path and then stops. If the player stops on a square with the bottom of a ladder, the player chooses whether or not to climb up that ladder. If she chooses not to climb, then she stays in that square for the beginning of the next turn.
- Some squares have a ladder in them. Ladders are only placed vertically — each one leads to the same square of some of the upper rows. In order for the player to climb up a ladder, after rolling the dice, she must stop at the square containing the bottom of the ladder. After using the ladder, the player will end up in the square containing the top of the ladder. She cannot leave the ladder in the middle of climbing. And if the square containing the top of the ladder also contains the bottom of another ladder, she is not allowed to use that second ladder.
- The numbers on the faces of the dice are 1, 2, 3, 4, 5, and 6, with each number having the same probability of being shown.
Please note that:
- it is possible for ladders to overlap, but the player cannot switch to the other ladder while in the middle of climbing the first one;
- it is possible for ladders to go straight to the top row, but not any higher;
- it is possible for two ladders to lead to the same tile;
- it is possible for a ladder to lead to a tile that also has a ladder, but the player will not be able to use that second ladder if she uses the first one;
- the player can only climb up ladders, not climb down.
Hyakugoku wants to finish the game as soon as possible. Thus, on each turn she chooses whether to climb the ladder or not optimally. Help her to determine the minimum expected number of turns the game will take.Input
Input will consist of ten lines. The i-th line will contain 10 non-negative integers \(h_{i1}, h_{i2}, \dots, h_{i10}\). If \(h_{ij}\) is 0, then the tile at the i-th row and j-th column has no ladder. Otherwise, the ladder at that tile will have a height of \(h_{ij}\), i.e. climbing it will lead to the tile \(h_{ij}\) rows directly above. It is guaranteed that \(0 \leq h_{ij} < i\). Also, the first number of the first line and the first number of the last line always contain 0, i.e. the Goal and the starting tile never have ladders.Output
Print only one line containing a single floating-point number — the minimum expected number of turns Hyakugoku can take to finish the game. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).
Examplesinput
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output
33.0476190476
input
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9
output
20.2591405923
input
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 6 6 6 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output
15.9047592939
Note
A visualization of the path and the board from example 2 is as follows:
The tile with an 'S' is the starting tile and the tile with an 'E' is the Goal.
For the first example, there are no ladders.
For the second example, the board looks like the one in the right part of the image (the ladders have been colored for clarity).
It is possible for ladders to overlap, as is the case with the red and yellow ladders and green and blue ladders. It is also possible for ladders to go straight to the top, as is the case with the black and blue ladders. However, it is not possible for ladders to go any higher (outside of the board). It is also possible that two ladders lead to the same tile, as is the case with the red and yellow ladders. Also, notice that the red and yellow ladders lead to the tile with the orange ladder. So if the player chooses to climb either of the red and yellow ladders, they will not be able to climb the orange ladder. Finally, notice that the green ladder passes through the starting tile of the blue ladder. The player cannot transfer from the green ladder to the blue ladder while in the middle of climbing the green ladder.
概率DP，先将每个点从终点开始编号，令\(dp[i]\)表示从i号点到终点的最小期望，显然\(dp[1]=0\);
如果不考虑梯子和终点的限制，那么\(dp[x]=\frac{\sum_{i=1}^{6}dp[x-i]}{6}+1\);
对于\(x<=6\)的情况需要特殊考虑，我们发现对于\(x=2\)，我们有\(\frac{5}{6}\)的概率不走，有\(\frac{1}{6}\)的概率走到终点，即\(dp[2]=\frac{5(dp[2]+1)}{6}+\frac{dp[1]+1}{6}\)；
移项之后就是\(dp[2]=\frac{(\frac{5}{6}+\frac{dp[1]+1}{6})} { (1-\frac{5}{6})}\)；
同理，\(dp[3]=\frac{(\frac{4}{6}+\frac{dp[1]+1}{6}+\frac{dp[2]+1}{6})}{(1-\frac{4}{6})}\)；
于是我们得到对于\(x\in [2,6]\)，我们有\(dp[x]=\frac{\frac{(\sum_{i=1}^{x-1}dp[x-i]+1)}{6}+\frac{(7-i)}{6}}{1-\frac{(7-i)}{6}}\)；
然后考虑加上梯子的情况，假设有一个梯子使得点x移动到y，那么\(dp[y]\)再考虑过一个从\(dp[x]\)转移来的情况就好了；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int id[110][110],to[110];
double dp[110];
int main(){
int tot=0;
rep(i,1,10){
if(i&1) rep(j,1,10) id[i][j]=++tot;
else dep(j,10,1) id[i][j]=++tot;
}
rep(i,1,10) rep(j,1,10){
int x;scanf("%d",&x);
if(x) to[id[i][j]]=id[i-x][j];
}
rep(i,2,6){//预处理x<6的情况
rep(j,1,i-1) dp[i]+=(dp[i-j]+1.0)/6;
dp[i]=(dp[i]+(7.0-i)/6)/(1.0-(7.0-i)/6);
}
rep(i,7,tot){
rep(j,1,6) dp[i]+=(dp[i-j]+1.0)/6;
if(!to[i]) continue;
double tmp=0;
if(to[i]==1){dp[i]=0;continue;}
rep(j,1,6) if(to[i]-j>0) tmp+=(dp[to[i]-j]+1.0)/6;
if(to[i]<=6) tmp+=(7.0-to[i])/6,tmp/=(1.0-(7.0-to[i])/6);
dp[i]=min(dp[i],tmp);
}
printf("%.10f\n",dp[tot]);
}
F. Daniel and Spring Cleaning
time limit per test2 seconds memory limit per test256 megabytes
While doing some spring cleaning, Daniel found an old calculator that he loves so much. However, it seems like it is broken. When he tries to compute 1 + 3 using the calculator, he gets 2 instead of 4. But when he tries computing 1 + 4, he gets the correct answer, 5. Puzzled by this mystery, he opened up his calculator and found the answer to the riddle: the full adders became half adders!
So, when he tries to compute the sum a + b using the calculator, he instead gets the xorsum \(a \oplus b\) (read the definition by the link: https://en.wikipedia.org/wiki/Exclusive_or).
As he saw earlier, the calculator sometimes gives the correct answer. And so, he wonders, given integers l and r, how many pairs of integers (a, b) satisfy the following conditions:
$$a + b = a \oplus b$$ $$l \leq a \leq r$$ $$l \leq b \leq r$$
However, Daniel the Barman is going to the bar and will return in two hours. He tells you to solve the problem before he returns, or else you will have to enjoy being blocked.
Input
The first line contains a single integer t \((1 \le t \le 100)\) — the number of testcases.
Then, t lines follow, each containing two space-separated integers l and r \((0 \le l \le r \le 10^9)\).
Output
Print t integers, the i-th integer should be the answer to the i-th testcase.
Exampleinput
3 1 4 323 323 1 1000000
output
8 0 3439863766
Note
\(a \oplus b\) denotes the bitwise XOR of a and b.
For the first testcase, the pairs are: (1, 2), (1, 4), (2, 1), (2, 4), (3, 4), (4, 1), (4, 2), and (4, 3).
首先将\(a + b = a \oplus b\)转换为\(a\&b==0\)，证明很好证，异或其实就是不进位的减法，那一加一减相等那肯定只有两个数对应的二进制都不同为1的情况才可以；
接下来考虑一个容斥，令f(l,r)表示\(a \in [1,l] ,b \in [1,r]\)时的答案，那么最终答案显然就是\(f(l-1,l-1)+f(r,r)-2*f(l-1,r)\)
接下来就是正常的数位DP，没什么好说的
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
ll dp[40][2][2];
ll dfs(int l,int r,int pos,int lima,int limb){
if(pos<0) return 1;
if(dp[pos][lima][limb]!=-1) return dp[pos][lima][limb];
int ma=lima?((l>>pos)&1):1;
int mb=limb?((r>>pos)&1):1;
dp[pos][lima][limb]=0;
rep(i,0,ma) rep(j,0,mb) if((i&j)==0)
dp[pos][lima][limb]+=dfs(l,r,pos-1,lima&(i==ma),limb&(j==mb));
return dp[pos][lima][limb];
}
ll f(int l,int r){//a->[0,l],b->[0,r]，a&b==0的数量
if(l<0) return 0;
memset(dp,-1,sizeof(dp));
return dfs(l,r,log2(r+1),1,1);
}
void solve(){
int l,r;scanf("%d%d",&l,&r);
printf("%lld\n",f(l-1,l-1)+f(r,r)-2ll*f(l-1,r));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
