[数据结构与算法]8.9专题赛题解

8.9专题赛1（位运算+递归递推）

题记：这场比赛就很nice！为什么呢？哈哈，因为是我出的题嘻嘻！hhhhh

Ps:还有几道题明天写个详细一点的题解…hhh碎觉

B. 快速幂

HDU - 1061

题目：

给定一个正整数 N，请输出 N^N 的最右一位数字。

输入

输入包含多组测试数据。输入的第一行是单个整数 T，表示测试数据的组数。接下来是 T 组测试数据。

每组测试数据，包含单个正整数 N (1 <= N <= 1,000,000,000)。

输出

对于每组测试数据，请输出 N^N 的最右一位数字。

示例输入

2
3
4

示例输出

7
6       

提示

在第一组测试数据中，3 * 3 * 3 = 27，因此最右一位数字是 7。
在第二组测试数据中，4 * 4 * 4 * 4 = 256，因此最后一位数字是 6。        
 

思路：

快速幂

（查资料的时候发现了一位大佬的博客——链接：快速幂详解（通俗易懂！）_IAMLSL的博客-CSDN博客

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    while(n -- )
    {
        long long a, b, p = 10;
        cin >> a;
        b = a;

        long long res = 1;
        while(b)
        {
            if(b & 1) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }

        res %= 10;
        cout << res << endl;

    }
    
    return 0;
}

C. lowbit 运算

HDU - 1196

题目：

Given an positive integer A (1 <= A <= 100), output the lowest bit of A.

For example, given A = 26, we can write A in binary form as 11010, so the lowest bit of A is 10, so the output should be 2.

Another example goes like this: given A = 88, we can write A in binary form as 1011000, so the lowest bit of A is 1000, so the output should be 8.

Input

Each line of input contains only an integer A (1 <= A <= 100). A line containing “0” indicates the end of input, and this line is not a part of the input data.

Output

For each A in the input, output a line containing only its lowest bit.

Sample Input

26
88
0

Sample Output

2
8

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin >> n, n)
    {
        int lowbit = n & (-n);
        cout << lowbit << endl;
    }

    return 0;
}

D. 推公式（递推+快速幂）

HDU - 7018

题目：

Given a three-dimensional space of [1,n]×[1,n]×[1,n][1,n]×[1,n]×[1,n]. You’re required to place some 1×1×11×1×1 cubes to make this 3D space look n×nn×n square from above, from left and from front, while the plane xOyxOy stand for the ground and zz axis describes the height.

But placing these cubes must follow some restrictions. Obviously, it must obey the gravity laws. It means, when beneath a cube is empty, the height of this cube will drop one, until its height is exactly 11 (touch the ground) or there is another cube below it.

And besides that, placing cubes has some prices. If a cube is placed at an integer coordinate (x,y,z)(x,y,z), the price will be x×y2×zx×y2×z.

Now, satisfying all the requirements above, you’re required to calculate the minimum costs and the maximum costs.

Input

The first line contains an integer T(T≤15)T(T≤15). Then TT test cases follow.

For each test case, input a single integer nn per line, while satisfying 1≤n≤10181≤n≤1018.

Output

For each test case, output two lines. For the first line output the minimum costs mod 109+7mod 109+7. And for the second line, output the maximum costs mod 109+7mod 109+7.

Sample Input

1
2

Sample Output

27
60

题意：

• 通过摆放若干个 $1\times 1\times 1$? 的小方块，填充 $n\times n\times n$? 的空间，使得从俯视图、正视图、侧视图都能看到完整的 $n\times n$? 的图形（方块受重力影响），每块小方块的代价为 $x\times y^2\times z$??? ，由此计算出最大代价和最小代价。

分析：

• 对于最大代价的情况，显然我们要填满 $n\times n\times n$???? 的空间，并且为了最大化代价，需要将每一个小方块从最高处丢下，因此有最大代价 $$n^2\times \frac{(n+1)n}{2}\times \frac{n\times (n+1)\times (2n+1)}{6}$$

• 对于最小代价的情况，由于重力的作用，需要将底面全部铺满。为满足其他两个视角，还需要立一面随着 $x$?? 递增，$y$?? 递减的竖墙。因此有最小代价 $$\frac{(1+n)\times n}{2}\times \frac{n\times (n+1)\times (2n+1)}{6}+\frac{(n^2+n?2)\times (n\times (n+1)\times (n+2)?6}{6}$$???

注意：

处理分母需要用到快速幂以及费马小定理求出逆元。

平方求和公式：$$\frac{n(n+1)(2n+1)}{6}$$?

AC代码：

#include<iostream>
#include<cstdio>

using namespace std;

const long long mod=1e9+7;

long long qpow(long long a,long long b)
{
	long long ans=1;
	while(b)
{
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1; 
	}
	return ans;
}

int main(){
	int T;
	cin>>T;
	long long n;
	while(T--)
{
		scanf("%lld",&n);
		n=n%mod; 
		
		long long a=n*(n+1)%mod*qpow(2,mod-2)%mod;
		long long b=n*(n+1)%mod*(2*n+1)%mod*qpow(6,mod-2)%mod;
		long long c=(n-1)%mod*(n+2)%mod*qpow(2,mod-2)%mod;

		long long ans1=a*b%mod+c*c%mod+b*c%mod-c;
		cout<<ans1%mod<<endl;
		
		long long ans2=a*b%mod*n%mod*n%mod;
		cout<<ans2%mod<<endl;
		
	}
	return 0;
}

注：

这里再补充一道快速幂求逆元的题目——AcWing 876.快速幂求逆元

and，Mallknow的题解写的很棒！

F. 异或基础

Gym - 100741D

题目：

You’re given an array a with n elements.

Compute the xor sum of the elements that appear an odd number of times in the array a.

Input

The first line contains number n (1?≤?n?≤?3000000). The second line of the input contains n numbers, representing the array a. All elements of a are between 0 and 109

Output

The only line of the output contains the answer of the problem.

Examples

Input

5
4 4 3 3 4

Output

4

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    cout << res << endl;

    return 0;
}