A-牛牛的DRB迷宫 I

题目描述

牛牛有一个 n×mn\times m 的迷宫，对于迷宫中的每个格子都为 ‘R’,‘D’,‘B’ 三种类型之一，'R’表示处于当前的格子时只能往右边走’D’表示处于当前的格子时只能往下边走，而’B’表示向右向下均可以走。
我们认为迷宫最左上角的坐标为 (1,1)(1,1)，迷宫右下角的坐标为 (n,m)(n,m)，除了每个格子有向右移动以及向下移动的限制之外，你也不能够走出迷宫的边界。
牛牛现在想要知道从左上角走到右下角不同种类的走法共有多少种，请你告诉牛牛从 (1,1)(1,1) 节点移动到 $(n,m) $ 节点共有多少种不同的移动序列，请你输出方案数对 $10^9+7 $ 取余数后的结果。
我们认为两个移动序列是不同的，当且仅当移动序列的长度不同，或者在某一步中采取了不同的移动方式。

输入描述

第一行输入两个正整数n,m(1≤n,m≤50)n,m(1≤n,m≤50)表示迷宫的大小是 nn 行 mm 列。
接下来n行，每行输入一个长度为m的字符串，字符串中仅包含大写字母’D’,‘R’,‘B’。

输出描述

输出一行一个整数，表示方案数对109+710^9+7取余数后的结果。

示例1

输入
5 5
RBBBR
BBBBB
BBBDB
BDBBB
RBBBB
输出
25

思路1

动态规划。当遍历到地图上的一个点(i,j)时，我们只知道下一步该怎么走，我们只能利用dp[i][j]dp[i][j]推出dp[i+1][j]dp[i+1][j]和dp[i][j+1]dp[i][j+1]。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#define ll long long
#define N 60
using namespace std;
const ll mod=1e9+7;
int n,m; 
ll dp[N][N];
char map[N][N];
int main()
{
	ios::sync_with_stdio(0);
	int i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>map[i][j];
		}
	}
	dp[1][1]=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(map[i][j]=='R') dp[i][j+1]=(dp[i][j+1]+dp[i][j]%mod)%mod;//只能往右走，向右累加。
			else if(map[i][j]=='D')dp[i+1][j]=(dp[i+1][j]+dp[i][j]%mod)%mod;//只能往下走，向下累加。
			else//两边都可以走。
			{
				dp[i][j+1]=(dp[i][j+1]+dp[i][j]%mod)%mod;
				dp[i+1][j]=(dp[i+1][j]+dp[i][j]%mod)%mod;
			}
		}
	}
	cout<<dp[n][m]%mod;
	return 0;
}

思路2

可以整活记忆化搜索。虽然没有直接dp方便，但是个人觉得这个方法很有价值，也很有思想深度。
我们非常的骚，我们倒着走，从(n,m)(n,m)走到(1,1)(1,1)，因为我们处于(x,y)(x,y)时，只知道是怎样走到(x,y+1),(x+1,y)(x,y+1),(x+1,y)，却不知道我们从前是怎样走到(x,y)(x,y)，人生有时也是这样！

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstring>
#define ll long long 
#define N 60
using namespace std;
ll dp[N][N];
const ll mod=1e9+7;
int n,m;
char map[N][N];
ll dfs(int x,int y)
{
    if(x>n||y>m||x<1||y<1) return 0;
    else 
    {
        if(dp[x][y]!=-1) return dp[x][y];
        else 
        {
            if(map[x][y]=='R') dp[x][y]=dfs(x,y+1);
            else if(map[x][y]=='D') dp[x][y]=dfs(x+1,y);
            else dp[x][y]=(dfs(x,y+1)+dfs(x+1,y))%mod;
            return dp[x][y];
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>map[i][j];
        }
    }
    memset(dp,-1,sizeof(dp));
    dp[n][m]=1;
    cout<<dfs(1,1);
}

B-牛牛的DRB迷宫 II

题目描述

牛牛有一个n×mn×m的迷宫，对于迷宫中的每个格子都为’R’,‘D’,'B’三种类型之一，'R’表示处于当前的格子时只能往右边走’D’表示处于当前的格子时只能往下边走，而’B’表示向右向下均可以走。
我们认为迷宫最左上角的坐标为(1,1)(1,1)，迷宫右下角的坐标为(n,m)(n,m)，除了每个格子有向右移动以及向下移动的限制之外，你也不能够走出迷宫的边界。
牛牛现在请你设计迷宫，但是要求你设计的迷宫符合他的要求，他要求你设计的迷宫从(1,1)节点移动到(n,m)(n,m)节点不同的移动序列种类数目≡k(mod109+7)k(mod10^9+7)。
请你构造出符合条件的DRB迷宫，但是要求你输出的迷宫的大小不超过50×5050×50，具体输出格式见输出描述及样例。
如果存在多解你可以构造任意符合条件的迷宫，反之如果无解，请输出一行一个字符串"No solution"。

输入描述

仅一个整数k，你需要构造一个DRB迷宫符合从左上走到右下的方案数≡k(mod109+7)≡k(mod10^9+7)。

输出描述

请你构造出符合条件的DRB迷宫,但是要求你输出的迷宫的大小不超过50×50。
第一行输出n,m两个整数，中间用空格隔开。
接下来n行，每行输出一个大小为m的字符串，字符串只能包含大写字母’D’,‘R’,‘B’。
如果存在多解你可以构造任意符合条件的迷宫，反之如果无解，请输出一行一个字符串"No solution"。

示例1

输入
25
输出
5 5
RBBBR
BBBBB
BBBDB
BDBBB
RBBBB

思路

此题非常巧妙地构造了一个二进制编码器。

用二进制可以拼出所有的数字，所以问题一定"Has one or more than one solutions"。
不妨来看一个极端的例子，k=1。
可以看到对角线上的一串B被R包围，当处于对角线上的一点时，如果选择向右，那么就会一直向右直到撞墙，如果向下，那么又会被弹回来。走到终点只有一种方法，那就是在第一个缺口往下跳，被底部的一串R接住。
有一种更极端的情况，k=0，那么斜对角线的B会被R完全包裹住，不留缺口。
斜对角线上的B自顶向下代表着1,2,4,8…如果B周围没有R包着，那么每次处于对角线的位置都有两个选择，跳或者不跳，越往后的选择对于总的方法的贡献越大。
我们不妨把k拆成二进制，从最末位开始查找，如果第j位是0，则在[j+1][j][j+1][j]处将字符更改为R，让下一步放弃跳的选择。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<iostream>
#define N 55
using namespace std;
const int n=50,m=30;
const int mod=1e9+7;
char map[N][N];
int main()
{
	int i,j;
	map[n][m]='B';
	for(j=1;j<=m;j++)
	{
		if(j<=2) map[1][j]='B';
		else map[1][j]='R';
	}
	for(i=2;i<=n-1;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(j>i+1) map[i][j]='R';
			else if(j<i-1) map[i][j]='D';
			else map[i][j]='B'; 
		}
	}
	int k;
	scanf("%d",&k);//既然方法数只要求同余，干脆取余就完事了。
	k=k%mod;
	for(j=1;j<=m;j++)
	{
		if(!(k&(1<<(j-1)))) map[j+1][j]='R';
		map[n][j]='R';//最后一行一串R用来输送
	}
	cout<<n<<' '<<m<<endl;
	for(i=1;i<=n;i++) printf("%s\n",map[i]+1);
	return 0;
}

C-牛牛的数组越界

题目描述

在C/C++中，数组越位行为是Undefined Behaviour(UB)的，也就是程序未定义行为，但是在牛牛的编译器呢，对于这种情况，二维数组的内存是连续的。
也就是说对于二维数组int a[5][5]a[5][5]，在牛牛的电脑中是按照a[0][0],a[0][1],a[0][2],a[0][3],a[0][4],a[1][0]...a[1][4],a[2][0]...a[2][4],a[3][0]...a[4][4]a[0][0],a[0][1],a[0][2],a[0][3],a[0][4],a[1][0]...a[1][4],a[2][0]...a[2][4],a[3][0]...a[4][4]
这样储存的。
牛牛所使用的编译器在寻址时是这样处理的，对于一个二维数组a[n][m]a[n][m]，若对a[x][y]a[x][y]这个数组元素进行操作，最终访问到的地址为：a的首地址+m﹡x+ya的首地址+m﹡x+y。
所以在寻址时，无论是a[−1][8]a[-1][8]还是a[1][−2]a[1][-2]最终在牛牛的电脑上使用该编译器编译出的程序均未发生非法访问的行为，他们最终都表示a[0][3]a[0][3]这个数组元素。
本题有T组测试数据。
牛牛先声明了一个n×m的int 型数组，即int a[n][m]a[n][m]，这个数组被他声明成一个全局变量，所以数组的初值全为0，接下来他要进行p次赋值运算。
每次他都选择一个二维下标x,y，并且把a[x][y]a[x][y]赋值成valval。
当然，牛牛不会老老实实按照C语言的规范来写代码。
如果这p次赋值操作中不存在数组越位行为，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Accepted"（不含引号），表示正常运行。
如果这p次赋值操作中虽然存在数组越位行为但是没有发生非法访问，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Undefined Behaviour"（不含引号），表示虽然能够运行，但是牛牛的代码不规范存在隐患。
如果这p次赋值操作中出现了至少一次数组越位并且导致非法访问的行为，请输出一行一个字符串"Runtime error"（不含引号）。

输入描述

第一行是一个正整数T(1≤T≤1000)T(1≤T≤1000)表示测试样例的组数且保证∑n×m≤2×107∑n×m≤2×10^7且∑p≤2×107∑p≤2×10^7。
对于每组案例：
第一行是三个正整数n,m,p(1≤n,m≤1000,0≤p≤100000)表示牛牛在全局中声明了一个int型的a数组，即int a[n][m]a[n][m];接下来牛牛准备进行p次赋值操作。
接下来p行，每行三个整数：$ x,y,val(−1000000≤x,y,val≤1000000)表示进行一次赋值操作，即表示进行一次赋值操作，即a[x][y]=val$。

输出描述

如果这p次赋值操作中不存在数组越位行为，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Accepted"（不含引号），表示正常运行。
如果这p次赋值操作中虽然存在数组越位行为但是没有发生非法访问，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Undefined Behaviour"（不含引号），表示虽然能够运行，但是牛牛的代码不规范，存在隐患。
如果这p次赋值操作中出现了至少一次数组越位并且导致非法访问的行为，请输出一行一个字符串"Runtime error"（不含引号）。

示例1

输入
4
2 4 8
-1 4 1
1 -3 2
2 -6 3
0 3 4
-1 8 5
-2 13 6
-100 406 7
100 -393 8
5 5 1
-1 8 1234
10 10 1
5 -51 1
1 1 1
0 0 7
输出
1 2 3 4
5 6 7 8
Undefined Behaviour
0 0 0 1234 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Undefined Behaviour
Runtime error
7
Accepted

备注

无论是否发生数组越位或者非法访问，输入数据都要完整读入。
题目中的代码不符合C/C++规范，在不同编译器中由于实现不同运行的结果也可能不同，请勿依赖特定编译器对于UB的实现。

思路

设一个flag标志，按照题目说的三种情况模拟就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1001][1001];
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        int n,m,p;
        cin>>n>>m>>p;
        memset(a,0,sizeof(a));
        int x,y,v;
        int flag=1;
        while(p--)
        {
            cin>>x>>y>>v;
            if (flag==3) continue;
            int i=(x*m+y)/m;
            int j=(x*m+y)%m;
            if (flag!=3)
            {
                if (i<0||i>=n||j<0||j>=m)
                {
                    flag=3;
                    continue;
                }
                else if(x<0||y<0) flag=2;
            }
            a[i][j]=v;
        }
        if (flag==3)
        {
            cout<<"Runtime error"<<endl;
            continue;
        }
        int i,j;
        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                cout<<a[i][j];
                if (j==m-1) cout<<endl;
                else cout<<' ';
            }
        }
        if (flag==1) cout<<"Accepted"<<endl;
        else if (flag==2) cout<<"Undefined Behaviour"<<endl;
    }
    return 0;
}

D-牛牛与二叉树的数据存储

题目描述

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。
当一颗二叉树是满二叉树时，可以用如下的规则储存：
数组0下标不使用
1.节点i的左子节点在位置为(2⋅i)(2·i);
2.节点i的右子节点在位置为(2⋅i+1)(2·i+1);
3.节点i的父节点在位置为(i/2)(i/2);
3.根节点被保存到数组下标为1的位置。

上图是一颗满二叉树，对于每个节点i，i·2是它的左子树，i·2+1是它的右子树，i/2则是它的父亲节点。
当然了，当树不为满二叉树的时候其实也能储存。

上图是树不为满二叉树的情况，我们先用一些虚点将其补充成一颗满二叉树。
根节点还是被储存到数组的第1个位置。
然后对于下标为i的节点，他的左孩子的下标为i·2，它的右孩子的下标为i·2+1，它的父亲节点的下标为i/2。
给你一个长度为n的数组，该数组储存了一颗二叉树，数组中仅含有-1和正整数，且整个数组中的正整数是从1到树尺寸连续的，不会出现如1,2,3,5,6，这种缺少4断掉的情况。
请你告诉我树的尺寸和根节点，并按照顺序打印每个节点的父亲节点、左孩子、右孩子分别是谁？

输入描述

第一行是一个正整数n(1≤n≤105)n(1≤n≤10^5)，表示数组的大小。
接下来一行nn个整数，仅包含−1-1和正整数，如果输入的是−1-1，则表示该位置是空节点，反之则为节点编号。输入数据保证整个数组中节点编号是从1到树尺寸连续的。

输出描述

对于每组案例：
首先在第一行输出：“The size of the tree is X”，X表示树的尺寸，树的尺寸为二叉树中节点的数目。
接着在第二行输出：“Node X is the root node of the tree”，X表示二叉树的根节点，也就是数组下标1的位置所储存的节点。
接下来输出size行，size表示树的尺寸。
每行格式为：“The father of node I is X, the left child is Y, and the right child is Z”,I、X、Y、Z的含义为：第I个节点的父节点为X，它的左孩子为Y，它的右孩子为Z。
如果该节点是根节点，没有父亲节点，则X为-1。
如果该节点没有左孩子，则Y为-1。
如果该节点没有右孩子，则Z为-1。

示例1

输入
7
1 2 3 4 5 6 7
输出
The size of the tree is 7
Node 1 is the root node of the tree
The father of node 1 is -1, the left child is 2, and the right child is 3
The father of node 2 is 1, the left child is 4, and the right child is 5
The father of node 3 is 1, the left child is 6, and the right child is 7
The father of node 4 is 2, the left child is -1, and the right child is -1
The father of node 5 is 2, the left child is -1, and the right child is -1
The father of node 6 is 3, the left child is -1, and the right child is -1
The father of node 7 is 3, the left child is -1, and the right child is -1

示例2

输入
7
3 -1 2 -1 -1 1 4
输出
The size of the tree is 4
Node 3 is the root node of the tree
The father of node 1 is 2, the left child is -1, and the right child is -1
The father of node 2 is 3, the left child is 1, and the right child is 4
The father of node 3 is -1, the left child is -1, and the right child is 2
The father of node 4 is 2, the left child is -1, and the right child is -1

思路

二叉树我没怎么看过，但是我会线段树啊！而且题目说得很清楚了。
我们只要记录每一个值的id，然后按照题目要求顺序输出就可以了，题目要求每个节点的值由大到小输出，不太懂它为什么要这么输出。
稍微有点坑的地方是要先把所有点赋值为-1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#define N 100008
using namespace std;
int tree[N<<1];
int id[N<<1];
int main()
{
	int n;
	scanf("%d",&n);
	memset(tree,-1,sizeof(tree));
	int ans=0;
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&tree[i]);
		if(tree[i]!=-1)
		{
			ans++;
			id[tree[i]]=i;
		}
	}
	printf("The size of the tree is %d\n",ans);
	printf("Node %d is the root node of the tree\n",tree[1]);
	for(i=1;i<=n;i++)
	{
		if(tree[id[i]]==-1) continue;
		else  printf("The father of node %d is %d, the left child is %d, and the right child is %d\n",tree[id[i]],tree[id[i]>>1],tree[id[i]<<1],tree[id[i]<<1|1]);
	} 
	return 0;
}

E-牛牛的随机数

题目描述

牛牛和牛可乐是一对好朋友，现在牛牛从值域[l1,r1][l_1,r_1]中随机给出一个数字a，牛可乐从值域[l2,r2][l_2,r_2]中随机给出一个数字b。问你a⊕ba\oplus b的数学期望。其中⊕⊕为位运算符，表示按位取异或。
为了避免你输出的答案出现精度误差，请你输出一个分数P×Q−1(mod  109+7)P×Q^{-1}(mod\,\, 10^9+7)，其中Q−1Q^{-1}Q表示在mod 条件下的乘法逆元。数据保证gcd(Q,109+7)=1gcd(Q,10^9+7)=1\，也就是说保证Q−1Q^{-1}
在该模条件下有意义,并且保证(r1−l1+1)(r2−l2+1)(r_1-l_1+1)(r_2-l_2+1)不是mod的倍数。

输入描述

第一行是一个正整数T(1≤T≤105)T(1 \leq T \leq 10^5)表示有TT组案例。
接下来TT行，每行四个正整数l1,r1,l2,r2(1≤l1≤r1≤1018,1≤l2≤r2≤1018)l_1,r_1,l_2,r_2(1 \leq l_1 \leq r_1 \leq 10^{18},1 \leq l_2 \leq r_2 \leq 10^{18})。

输出描述

请输出期望P×Q−1(mod  109+7)P×Q^{-1}(mod\,\, 10^9+7)。

示例1

输入
2
3 5 7 8
1 3 3 5
输出
500000011
222222228
说明
aa可取3,4,53,4,5，bb可取7,87,8。
3⊕7=4,4⊕7=3,5⊕7=2,3⊕8=11,4⊕8=12,5⊕8=133⊕7=4,4⊕7=3,5⊕7=2,3⊕8=11,4⊕8=12,5⊕8=13，
共6种情况，答案为(4+3+2+11+12+13)/6=45/6=15/2=15×2−1(mod   109+7)(4+3+2+11+12+13)/6=45/6=15/2=15×2^{-1}(mod \,\,\, 10^9+7)

备注

乘法逆元：Q−1(mod  109+7)≡Q109+5Q^{-1}(mod\,\, 10^9+7)\equiv Q^{10^9+5}

思路

非常显然，答案为$\frac{\sum_{x=l_1}^{r_1}\sum_{y=l_2}^{r_2}x\oplus y}{(r_1-l_1+1)(r_2-r_2+1\ )\ } $，就是枚举每种情况，然后除以方案总数。但是显然不能用两层循环暴力算这个。
异或操作只有在x,yx,y二进制的同一位为0,10,1时才对答案产生贡献。首先考虑二进制的个位产生的贡献，那么二进制个位产生的贡献有两部分：
[l1,r1][l_1,r_1]区间内个位为0的数字乘以[l2,r2][l_2,r_2]区间内个位为1的数字。
[l1,r1][l_1,r_1]区间内个位为1的数字乘以[l2,r2][l_2,r_2]区间内个位为0的数字。
假设x∈[l1,R1]x \in [l_1,R_1]中二进制的个位产生00的数目为cntx0cntx_0，二进制的个位产生11的数目为cntx1cntx_1；y∈[l2,R2]y \in [l_2,R_2]中二进制的个位产生0的数目为cnty0cnty_0，二进制的个位产生11的数目为cnty1cnty_1。那么就产生了cnty0×cntx1+cntx0×cnty1cnty_0×cntx_1+cntx_0×cnty_1的贡献。
如果是二进制的十位呢，那么就是2×(cnty0×cntx1+cntx0×cnty1)2×(cnty_0×cntx_1+cntx_0×cnty_1)。
那么二进制的第kk位的贡献就为2k×(cnty0×cntx1+cntx0×cnty1)2^k×(cnty_0×cntx_1+cntx_0×cnty_1)。
接下来的任务就是解决统计一个数字pp，每一位二进制位上11和00的个数。
我们不妨打个表找规律，于是整活了这样一段代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bitset>
#include<iostream>
using namespace std;
const int len=6;
int main()
{
	int i;
	for(i=0;i<=50;i++)
	{
		bitset<len>res(i);
		cout<<res<<endl;
	}
	return 0;
}

如图：

把所有的数字从0开始枚举，然后转化成二进制输出，我们发现二进制下个位的规律是010101…循环，十位是001100110011…循环，而百位是0000111100001111…循环。接下来的话就跟上面差不多。倒数第kk位循环长度是2k+12^{k+1}，每一次循环里00和11的个数都是2k2^k。
最后一步，我们用类似二维前缀和的东西把那一坨′∑′'∑'求出来了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll quick_pow(ll a,ll b,ll p=mod)//算逆元
{
	a%=p;
	if(a==0) return 0;
	else
	{
		ll res=1;
		while(b)
		{
			if(b&1) res=res*a%p;
			a=a*a%p;
			b>>=1;
		}
		return res%p;
	}
}
ll get_num_zero(ll p,ll bit)
{
	p++;//是从0开始记的，所以加1表示次序。
	ll res;
	ll temp=2ll<<bit;//0和1循环的长度
	res=(p/temp)/*循环次数*/*(1ll<<bit)/*每次循环包含0的个数*/%mod;
    res+=min(1ll<<bit,p%temp);//加上剩下的
	res=res%mod;
	return res;
}
ll get_num_one(ll p,ll bit)
{
	return (p+1-get_num_zero(p,bit)+mod)%mod;//减去0的个数就是1的个数
}
ll get_val(ll x,ll y)
{
	ll res=0;
	ll bit;
	for(bit=0;bit<=60;bit++)
	{
		ll temp=1ll<<bit;//每一位的贡献乘2^bit 
		temp%=mod;
        //计算两个区间选取的值为分别x,y的贡献
		res=(res+(get_num_zero(x,bit)*get_num_one(y,bit)%mod+get_num_zero(y,bit)*get_num_one(x,bit)%mod)%mod*temp)%mod;
	}
    return res;
}
void solve()
{
	ll l1,r1,l2,r2;
	cin>>l1>>r1>>l2>>r2;
	ll ans;
    //利用异或的二维前缀和性质得到所有可能性的和
	ans=get_val(r1,r2)-get_val(r1,l2-1)+get_val(l1-1,l2-1)-get_val(l1-1,r2);
	ans=(ans%mod+mod)%mod;
	ll temp=(((r1-l1+1)%mod)*((r2-l2+1)%mod))%mod;
	ans=(ans*quick_pow(temp,mod-2))%mod;
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

题目描述

牛牛有一颗大小为n的神奇Link-Cut 数组，数组上的每一个节点都有两种状态，一种为link状态，另一种为cut状态。数组上任意一对处于link状态的无序点对（即(u,v)和(v,u)被认为是同一对）会产生dis(u,v)的link能量，dis(u,v)为数组上u到v的距离。
我们定义整个数组的Link能量为所有处于link状态的节点产生的link能量之和。
一开始数组上每个节点的状态将由一个长度大小为n的01串给出，'1’表示Link状态，'0’表示Cut状态。
牛牛想要知道整个数组的Link能量，为了避免这个数字过于庞大，你只用输出答案对10⁹+7取余后的结果即可。

输入描述

第一行输入一个正整数n(1≤n≤105)n(1≤n≤10^5)
接下里一行输入一个长度大小为n的01串表示数组的初始状态，'1’表示Link状态，'0’表示Cut状态。

输出描述

仅一行，表示整个数组的Link能量对109+710^9+7取余后的结果。

示例1

输入
3
101
输出
2

示例2

输入
5
00110
输出
1

示例3

输入
6
000010
输出
0

思路1

设想一个循环:for(i=1 to n)。假设当前我们已经遍历至p，此时已经遇到cnt个’1’，我们不妨假设将来还会遇到一个’1’。i每前进一步，已经遍历到的01串的总link能量的贡献都会增加cnt，最后这个效应会叠加在将来遍历到的那个’1’上。
我们可以记录cnt与sum，cnt表示当前经过了多少个1,sum表示当前的贡献总和。
这个算法在复杂度上显得十分优秀，时间复杂度为(n)，空间复杂度O(1)。调试一遍下面的代码，就能明白其构思巧妙之处。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int main()
{
    const int mod=1000000007;
    int sum=0,cnt=0,ans=0;
    int n;
    cin>>n;
    int i;
    char c;
    for(i=1;i<=n;i++)
    {
        cin>>c;
        sum=(sum+cnt)%mod;
        if(c=='1')
        {
            cnt++;
            ans=(ans+sum)%mod;
        }
    }
    cout<<ans;
    return 0;
}

思路2

我们发现每个’1’对于它本身位置产生的影响贡献为0，而往后面依次产生了0,1,2,3,4,5…的贡献。有统计贡献的数组sum,所有元素初始值为0。
对于每个位置的1，假设它的位置为pos，那么直接对sum[pos+1]加上1的贡献。
全部做完以后，做两次前缀和操作，对于每个位置的’1’直接查询数组中的值加起来即可。
不妨来看一个例子，输入字符串"1000000"，遍历数组后sum为{0,1,0,0,0,0,0}。
一次前缀和操作后，有{0,1,1,1,1,1,1}。又一次前缀和操作后，有{0,1,2,3,4,5,6}。
通过简单的举例，能很直观得想到，将a[pos+1]=1操作完成后，得到的序列是sum的二阶差分，只需要执行两次前缀和操作就可还原。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#define N 100009
using namespace std;
const int mod=1e9+7;
int n;
char s[N];
int sum[N]={0};
void PreSum()
{
    int i;
    for(i=1;i<=n;i++) sum[i]=(sum[i]+sum[i-1])%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int i;
    for(i=1;i<=n;i++)
    {
        cin>>s[i];
        if(s[i]=='1') sum[i+1]=1;
    }
    PreSum();PreSum();
    int ans=0;
    for(i=1;i<=n;i++)
    {
        if(s[i]=='1') ans=(ans+sum[i])%mod;
    }
    cout<<ans;
    return 0;
}

题目描述

牛牛有一颗大小为n的神奇Link-Cut 数组，数组上的每一个节点都有两种状态，一种为link状态，另一种为cut状态。数组上任意一对处于link状态的无序点对（即(u,v)和(v,u)被认为是同一对）会产生dis(u,v)的link能量，dis(u,v)为数组上u到v的距离。
我们定义整个数组的Link能量为所有处于link状态的节点产生的link能量之和。
一开始数组上每个节点的状态将由一个长度大小为n的01串给出，'1’表示Link状态，'0’表示Cut状态。
牛牛想要知道一开始，以及每次操作之后整个数组的Link能量，为了避免这个数字过于庞大，你只用输出答案对1000000007取余后的结果即可。

输入描述

第一行输入一个正整数n(1≤n≤105)n(1≤n≤10^5)。
接下里一行输入一个长度大小为n的01串表示数组的初始状态，'1’表示Link状态，'0’表示Cut状态。
接下来一行输入一个正整数m(1≤m≤105)m(1≤m≤10^5)表示操作的数目。
接下来m行，每行输入两个正整数q,pos(q∈1,2,1≤pos≤n)q,pos(q∈{1,2},1≤pos≤n)。
当q=1时表示牛牛对数组的第pos个元素进行操作，将其赋值为1，保证在这个操作之前，该元素的值为0。
当q=2时表示牛牛对数组的第pos个元素进行操作，将其赋值为0，保证在这个操作之前，该元素的值为1。

输出描述

请输出m+1行表示一开始，以及每次操作之后整个数组的Link能量，为了避免这个数字过于庞大，你只用输出答案对109+710^9+7取余后的结果即可。

示例1

输入
5
00001
7
1 1
2 5
2 1
1 2
1 4
1 3
1 1
输出
0
4
0
0
0
2
4
10

思路

一看就要线段树啊。
假设我的序列为"1110001"。
那么如果我在5位置将0变为1，那么我会产生新的贡献即为(1,5),(2,5),(3,5)，(5,7) 也就是 5-1+5-2+5-3+7-5，我们不妨把这个式子拆成 3×5-(1+2+3)与7-1×5，观察5之前的系数，即为该位置之前1的个数，括号里的内容是一个1的位置的前缀和。
我们只需要维护两颗线段树一棵维护区间内1的个数，另一颗维护区间内1的位置的求和。
0->1对应的询问为:
ans+=query(cnt1,1,1,x-1)﹡pos-query(prefix_pos,1,1,x-1)//前面的1对位置pos产生的贡献
ans+=query(prefix_pos,1,x+1,n)-query(cnt1,1,x+1,n)﹡pos//后面的1对位置pos产生的贡献
1->0对应的询问为：
ans-=query(cnt1,1,1,x-1)﹡pos-query(prefix_pos,1,1,x-1)//前面的1对位置pos产生的贡献
ans-=query(prefix_pos,1,x+1,n)-query(cnt1,1,x+1,n)﹡pos//后面的1对位置pos产生的贡献
所以说具体的线段树修改操作我们只需要维护两种：
一种单点修改：update(Segment ﹡p,id,pos,w)//在p树下pos位置+w
一种区间查询：query(Segment ﹡p,id,x,y) //在p树下查询区间[x,y]的权值和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstdio>
#define N 1000001
#define ll long long
using namespace std;
const int mod=1e9+7;
struct Segment 
{
	int l,r;
	ll w;
};
Segment cnt1[N<<2];//区间内1的个数
Segment prefix_pos[N<<2];//区间内1的位置的求和
void build(Segment *p,int id,int l,int r)
{
	p[id].l=l;
	p[id].r=r;
	p[id].w=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p,id<<1,l,mid);
	build(p,id<<1|1,mid+1,r);
}
int n;
void update(Segment *p,int id,int pos,int w)
{
	if(p[id].l==p[id].r)
	{
		p[id].w=(p[id].w+w)%mod;
		return;
	}
	int mid=(p[id].l+p[id].r)>>1;
	if(pos<=mid) update(p,id<<1,pos,w);
	else update(p,id<<1|1,pos,w);
	p[id].w=(p[id<<1].w+p[id<<1|1].w)%mod;
}
ll query(Segment *p,int id,int x,int y)
{
	if(x<1||y>n) return 0;
	if(x<=p[id].l&&p[id].r<=y) return p[id].w;
	ll sum=0;
	int mid=(p[id].l+p[id].r)>>1;
	if(x<=mid) sum+=query(p,id<<1,x,y);
	if(y>=mid+1) sum+=query(p,id<<1|1,x,y);
	return sum;
}
char s[N];
ll init()
{
	scanf("%d%s",&n,s+1);
	int i;
	ll sum=0,cnt=0,res=0;
	for(i=1;i<=n;i++)
	{
		sum=(sum+cnt)%mod;
		if(s[i]=='1')
		{
			cnt++;
			res=(res+sum)%mod;
		}
	}
	return res;
} 
int main()
{
	ll ans=init();
	build(prefix_pos,1,1,n);
	build(cnt1,1,1,n);
	int i;
	for(i=1;i<=n;i++)
	{
		if(s[i]=='1')//单点更新 
		{
			update(cnt1,1,i,1);
			update(prefix_pos,1,i,i);
		}
	}
    int m;
    scanf("%d",&m);
	printf("%lld\n",ans);	
	while(m--)
	{
		int opt;
		int pos;
		ll one,sum;
		scanf("%d%d",&opt,&pos);
		if(opt==1)//link能量增加 
		{
			one=query(cnt1,1,1,pos-1);
			sum=query(prefix_pos,1,1,pos-1);
			ans=(ans+pos*one%mod-sum%mod+mod)%mod;
			one=query(cnt1,1,pos+1,n);
			sum=query(prefix_pos,1,pos+1,n);
			ans=(ans+sum%mod-one*pos%mod+mod)%mod;
			update(cnt1,1,pos,1);//pos位置1的个数加一
			update(prefix_pos,1,pos,pos);//pos位置1的位置的和加pos 			
		}
		else//link能量减少 
		{
			one=query(cnt1,1,1,pos-1);
			sum=query(prefix_pos,1,1,pos-1);
			ans=(ans-pos*one%mod+sum%mod+mod)%mod;
			one=query(cnt1,1,pos+1,n);
			sum=query(prefix_pos,1,pos+1,n);
			ans=(ans-sum%mod+pos*one%mod+mod)%mod;
			update(cnt1,1,pos,-1);
			update(prefix_pos,1,pos,-pos); 
		}
		printf("%lld\n",ans);
	}
	return 0;
}

H-牛牛的K合因子数

题目描述

合数是指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
牛牛最近在研究“k合因子数”，所谓“k合数”是指一个数的所有因子中，是合数的因子共有k个。
例如20的因子有1,2,4,5,10,20，其中4,10,20为合数，它有3个合数因子，就称20是一个 “3合因子数”
牛牛想要知道1~n中给定k的情况下k合因子数的数目。

输入描述

第一行输入两个数字n,m(1≤n,m≤10^5)表示范围以及查询“k”的数目。
接下来m行，每行一个正整数k表示(1≤k≤n)查询k合因子数的数目。

输出描述

一行一个数字，表示k合因子数的数目。

思路1

最暴力的想法是，枚举1~n的所有数字i，把i的因数j都找出来，判断j是不是合数。很显然，会TLE。
稍微好一些的方法是先找出1~n的所有合数，存入数组，然后枚举1~n的数字i，找到i的因子j，可以用O(1)的时间查询j是否为合数。而寻找i的因子，可在O(i)的时间完成。
寻找1~n的合数有很多方法：直接暴力枚举检验，埃氏筛，欧拉筛。所以总的时间复杂度为O(nn)O(n\sqrt n)。
于是我非常头脑简单的过了题。
其实感觉并不简单，还t了两次。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
#define N 100009
using namespace std;
int ans[N];
bool yes[N]={0};//是合数为true
int len=0;
bool judge(int x)
{
	int i;
	for(i=2;i<=sqrt(x);i++)
	{
		if(x%i==0) return 1;
	}
	return 0;
}
int f(int x)
{
	int ans=0;
	int i;	
	for(i=1;i<=sqrt(x);i++)
	{
		if(x%i==0)
		{
			if(yes[i]) ans++;
			if(i*i!=x&&yes[x/i]) ans++;
		}
	}
	return ans;
}
int main()
{
	
	int n,m;
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=1;i<=100000;i++) 
	{
		if(judge(i)) yes[i]=1;
	}
	for(i=1;i<=n;i++) 
	{
		ans[f(i)]++;
	}
	int t;
	for(i=1;i<=m;i++) 
	{
		scanf("%d",&t);
		printf("%d\n",ans[t]);
	}	
	return 0;
}

思路2

埃氏筛，一边划掉合数，一边统计个数。时间复杂度O(nlogn)O(nlogn)。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#define N 100002
using namespace std;
int ans[N],cnt[N]/*i的合因子个数*/;
bool prime[N];
int n,m;
void EratosthenesSieve()
{
    int i,j;
    for(i=2;i<=n;i++) prime[i]=true;
    for(i=2;i<=n;i++)
    {
        if(prime[i])
        {
           for(j=i<<1;j<=n;j+=i) prime[j]=false; 
        }
        else 
        {
            for(j=i;j<=n;j+=i) cnt[j]++;//i的倍数的因子又多了一个。          
        }
        ans[cnt[i]]++;//i的合因子个数计算完毕，合因子个数为cnt[i]的数字的个数又多了一个。
    }
}
int main()
{
    ios::sync_with_stdio(0);   
    cin>>n>>m;
    EratosthenesSieve();
    while(m--)
    {
        int t;
        cin>>t;
        cout<<ans[t]<<endl;
    }
    return 0;
}

思路3

我们来尝试用欧拉筛做题，我们当然可以像用埃氏筛那样，在划去合数的同时，统计某个数的合因子个数。然而这样时间复杂度并没有降低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void OlaSieve()
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		if(!vis[i]) v.push_back(i);
        else 
        {
            for(j=i;j<=n;j+=i) cnt[j]++;
        }
		for(j=0;j<v.size()&&i*v[j]<=n;j++)
		{
			vis[i*v[j]]=1;
			if(i%v[j]==0) break;
		}
        ans[cnt[i]]++;
	}
}

所以干脆把求合因子个数的事情放在欧拉筛外面吧。那这样就和第一种思路就很像了。我们在O(n)内解决了问题。

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstring>
#include<iostream>
#include<vector>
#define N 100009
using namespace std;
int ans[N],cnt[N];
bool vis[N];
vector<int>v;
int n,m;
void OlaSieve()
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		if(!vis[i]) v.push_back(i);
		for(j=0;j<v.size()&&i*v[j]<=n;j++)
		{
			vis[i*v[j]]=1;
			if(i%v[j]==0) break;
		}
	}
}
int main()
{
	cin>>n>>m;
	OlaSieve();
	v.clear();
	int i,j;
	for(i=1;i<=n;i++)
	{
		if(vis[i]) v.push_back(i);//把所有合数装进来
	}
	for(i=0;i<v.size();i++)
	{
		for(j=1;j*v[i]<=n;j++) cnt[v[i]*j]++;
	}
	for(i=1;i<=n;i++) ans[cnt[i]]++;
	while(m--)
	{
		int t;
		cin>>t;
		cout<<ans[t]<<endl;
	}
	return 0;
}

I-牛牛的汉诺塔

题目描述

汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
请你统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。

输入描述

仅一行，输入一个正整数n(1≤n≤60)表示汉诺塔的层数。

输出描述

首先输出6行
A->B:XX
A->C:XX
B->A:XX
B->C:XX
C->A:XX
C->B:XX
分别表示每种移动情况出现的次数
最后输出一行
SUM:XX
表示所有移动情况的总和。

示例1

输入
3
输出
A->B:1
A->C:3
B->A:1
B->C:1
C->A:0
C->B:1
SUM:7
说明
移动序列如下：
A->C
A->B
C->B
A->C
B->A
B->C
A->C
统计：
A->B出现1次
A->C出现3次
B->C出现1次
B->A出现1次
C->B出现1次
总计7次

思路1

记忆化搜索。啊！！怎么又没有想到。普通递归TLE的话，利用记忆化搜索能大大降低时间复杂度。
因为需要输出六种移动的次数，我们不妨定义结构体"way"，内含四个维度。令结构体way的数组dp[a−′A′][b−′A′][c−′A′][n]dp[a-'A'][b-'A'][c-'A'][n]为n个盘借助b从a移动到c的汉诺塔。为了记录dp数组是否已经在搜索中被赋值，我们不妨在结构体中添加vis的bool属性。
一切准备妥当后，只要用汉诺塔最基本的所谓"借助柱子中转的思想"进行记忆化搜索就好啦。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstring>
#include<iostream>
#define N 105
using namespace std;
struct way
{
	long long dat[6];
    bool vis;
	way()
	{
		memset(dat,0,sizeof(dat));
        vis=false;
	}
	/*
	A->B 0
	A->C 1
	B->A 2
	B->C 3
	C->A 4
	C->B 5
	*/
};
way operator + (const way& a,const way& b)
{
	way c;
	int i;
	for(i=0;i<6;i++) c.dat[i]=a.dat[i]+b.dat[i];
	return c;
}  
void move(char x,char y,way& temp)
{
	 if(x=='A'&&y=='B') temp.dat[0]++;
	 else if(x=='A'&&y=='C') temp.dat[1]++;
	 else if(x=='B'&&y=='A') temp.dat[2]++;
	 else if(x=='B'&&y=='C') temp.dat[3]++;
	 else if(x=='C'&&y=='A') temp.dat[4]++;
	 else if(x=='C'&&y=='B') temp.dat[5]++;
}
way dp[3][3][3][N];
way hanoi(char a,char b,char c,int n)
{
	if(dp[a-'A'][b-'A'][c-'A'][n].vis) return dp[a-'A'][b-'A'][c-'A'][n];
	if(n==1)
	{
		move(a,c,dp[a-'A'][b-'A'][c-'A'][1]);
        dp[a-'A'][b-'A'][c-'A'][1].vis=true;
        return dp[a-'A'][b-'A'][c-'A'][1];
	}
	way temp;
	temp=temp+hanoi(a,c,b,n-1);//借助c将n-1个盘子从a移到b
	move(a,c,temp);
	temp=temp+hanoi(b,a,c,n-1);//借助a将n-1个盘子从b移到c
	dp[a-'A'][b-'A'][c-'A'][n]=temp;
    dp[a-'A'][b-'A'][c-'A'][n].vis=true;
	return dp[a-'A'][b-'A'][c-'A'][n];
}
int main()
{
	ios::sync_with_stdio(0);
	int n;
	cin>>n;
	way ans=hanoi('A','B','C',n);
	printf("A->B:%lld\n", ans.dat[0]);
    printf("A->C:%lld\n", ans.dat[1]);
    printf("B->A:%lld\n", ans.dat[2]);
    printf("B->C:%lld\n", ans.dat[3]);
    printf("C->A:%lld\n", ans.dat[4]);
    printf("C->B:%lld\n", ans.dat[5]);
    //汉诺塔总步数：f(n)=1<<n-1。
    printf("SUM:%lld", ((long long)1<<(long long)n)-1);
}