# CF855E Salazar Slytherin's Locket
## 题面翻译
求$l...r$之间转成$b$进制后，$0,1,2...,b-2,b-1$都出现偶数次的数的个数。
第一行一个数$q$,为数据组数。
下面$q$行，每行$3$个整数，表示$b,l,r$。
$1\le q \le 10^5$
$2\le b \le 10$
$1\le l \le r \le 10^{18}$
输出，共$q$行，为每个询问的答案。
## 题目描述
Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and is now present in the Ministry of Magic in the office of Dolorous Umbridge, Harry's former Defense Against the Dark Arts teacher.
Harry, Ron and Hermione are infiltrating the Ministry. Upon reaching Umbridge's office, they observed a code lock with a puzzle asking them to calculate count of magic numbers between two integers $ l $ and $ r $ (both inclusive).
Harry remembered from his detention time with Umbridge that she defined a magic number as a number which when converted to a given base $ b $ , all the digits from $ 0 $ to $ b-1 $ appear even number of times in its representation without any leading zeros.
You have to answer $ q $ queries to unlock the office. Each query has three integers $ b_{i} $ , $ l_{i} $ and $ r_{i} $ , the base and the range for which you have to find the count of magic numbers.
## 输入格式
First line of input contains $ q $ ( $ 1<=q<=10^{5} $ ) — number of queries.
Each of the next $ q $ lines contain three space separated integers $ b_{i} $ , $ l_{i} $ , $ r_{i} $ ( $ 2<=b_{i}<=10 $ , $ 1<=l_{i}<=r_{i}<=10^{18} $ ).
## 输出格式
You have to output $ q $ lines, each containing a single integer, the answer to the corresponding query.
## 样例 #1
### 样例输入 #1
```
2
2 4 9
3 1 10
```
### 样例输出 #1
```
1
2
```
## 样例 #2
### 样例输入 #2
```
2
2 1 100
5 1 100
```
### 样例输出 #2
```
21
4
```
## 提示
In sample test case $ 1 $ , for first query, when we convert numbers $ 4 $ to $ 9 $ into base $ 2 $ , we get:
- $ 4=100_{2} $ ,
- $ 5=101_{2} $ ,
- $ 6=110_{2} $ ,
- $ 7=111_{2} $ ,
- $ 8=1000_{2} $ ,
- $ 9=1001_{2} $ .
Out of these, only base $ 2 $ representation of $ 9 $ has even number of $ 1 $ and $ 0 $ . Thus, the answer is $ 1 $ .
这题是数位DP题，一般数位dp第一维是当前位，第二维是附加状态。那么这题需要把各个位出现的次数模2压缩成状态。这题询问很多，因此需要一遍初始化。
接下来就是套模板。
```plaintext
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
using namespace std;
int f[100][1025][11];
int b,l,r;
int a[100];
int dfs(int len,int sta,int p,int q){//p:有无前导零 q:有无数位限制
if(!len) return !sta;
int& v=f[len][sta][b];
if(v!=-1&&!p&&!q) return v;
int y=q?a[len]:(b-1);
int ret=0;
rep(i,0,y){
ret+=dfs(len-1,(p&&!i)?0:((1<<i)^sta),p&&!i,q&&(i==y));
}
if(!p&&!q) v=ret;
return ret;
}
int los(int x){
int len=0;
while(x!=0){
a[++len]=x%b;
x/=b;
}
return dfs(len,0,1,1);
}
void sol(){
cin>>b>>l>>r;
cout<<los(r)-los(l-1)<<'\n';
}
int32_t main(){
memset(f,-1, sizeof f);
int T;cin>>T;
while(T--)
sol();
}
# Travelling Salesman and Special Numbers
## 题面翻译
对于一个正整数x，我们定义一次操作是将其变为它二进制下“1”的个数,比如我们知道$13_{10}$=$1101_2$ ,而1101有三个"1",所以对13进行一次操作就会将其变为3。显而易见的是，对于一个正整数，我们在进行若干次操作后，一定会将其变为1。
给定n和kk，其中n是在二进制下被给出，求出所有不大于n且将其变为1的最小操作次数为kk的数的个数对$10^9+7$取模的结果。
## 题目描述
The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer $ x $ and reduce it to the number of bits set to $ 1 $ in the binary representation of $ x $ . For example for number $ 13 $ it's true that $ 13_{10}=1101_{2} $ , so it has $ 3 $ bits set and $ 13 $ will be reduced to $ 3 $ in one operation.
He calls a number special if the minimum number of operations to reduce it to $ 1 $ is $ k $ .
He wants to find out how many special numbers exist which are not greater than $ n $ . Please help the Travelling Salesman, as he is about to reach his destination!
Since the answer can be large, output it modulo $ 10^{9}+7 $ .
## 输入格式
The first line contains integer $ n $ ( $ 1<=n<2^{1000} $ ).
The second line contains integer $ k $ ( $ 0<=k<=1000 $ ).
Note that $ n $ is given in its binary representation without any leading zeros.
## 输出格式
Output a single integer — the number of special numbers not greater than $ n $ , modulo $ 10^{9}+7 $ .
## 样例 #1
### 样例输入 #1
110
2
### 样例输出 #1
3
## 样例 #2
### 样例输入 #2
111111011
2
### 样例输出 #2
169
## 提示
In the first sample, the three special numbers are $ 3 $ , $ 5 $ and $ 6 $ . They get reduced to $ 2 $ in one operation (since there are two set bits in each of $ 3 $ , $ 5 $ and $ 6 $ ) and then to $ 1 $ in one more operation (since there is only one set bit in $ 2 $ ).
这题细节比较多。首先观察到处理完一次后这题