Post 87

Veröffentlicht am

越来越菜，越菜越来。

毒瘤之神异之旅

题目背景

题目名称是吸引你点进来的……

我们的出题人CYJian由于出了过多毒瘤题被D死之后，OIer们将他埋葬在地狱十八层之下……

题目描述

已知地狱有KK个守护者,每个守护者有一个能力值a_ia**i。但是我们并不知道他们确切的能力值。只知道这些人的能力值的和为NN。但是在地狱中守护者的威力会得到加强，具体来说每一个守护者的威力为a_i^MaiM。

现在给出NN,MM,KK,请求出所有可能的方案的威力值之和。

输入输出格式

输入格式：

一行三个整数NN，KK和MM。

输出格式：

一行一个整数，表示所有守护者能够发出的可能的威力值之和模1e9+71e9+7。

输入输出样例

输入样例#1：

1
5 2 3

输出样例#1：

1
100

输入样例#2：

1
7 3 1

输出样例#2：

1
28

说明

Subtask1(20 pts):

$1 \leq N,M \leq 10$

$1 \leq K \leq N$

Subtask 2(40 pts):

$1 \leq N,M \leq 4096$

$1 \leq K \leq N$

Subtask 3(40 pts):

$1 \leq N,M \leq 10000$

$1 \leq K \leq N$

其中所有的$a_i$均需要是正整数.

题解

注意到样例给的是不重复的分拆序列次幂和。

我们可以强制不降序，这样使得所有重复同构的都变成了一个。

然后就5分钟写出一个爆搜获得第一个Subtask的分。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
const int mod = (int)1e9+7;
int n , m , k ,ans;

inline int pow(int x , int y)
{
	int ans = 1 , base = x;
	for( ; y ; y >>= 1 , base = 1ll * base * base)
		if(y & 1)
			ans = 1ll * ans * base % mod;
	return ans;
}

void dfs(int cur , int r , int x , int la)
{
	if(!r)
	{
		if(x == k + 1) ans = ans + cur , ans %= mod;
		return;
	}
	for(int i = la ; i <= r ; ++i)
		dfs(cur + pow(i , m) , r - i , x + 1 , i);
}


int main()
{
	scanf("%d%d%d",&n,&k,&m);
	dfs(0 , n , 1 , 1);
	printf("%d\n",ans);
}

然后就不会了。。。

签到

题目描述
求$\sum{i=1}^n \sum{j=1}^n [i \ xor \ j \in [\min(i,j),\max(i,j)]]$

由于答案可能过大，输出答案对10^9+7109+7取模的值。

输入输出格式

输入格式：

第一行，一个整数T，为数据组数。

下面T行，每行一个整数n。

输出格式：

对于每行数据，输出答案。

输入输出样例

输入样例#1：

1
2
3
4
3
10
100
1000

输出样例#1：

1
2
3
20
2634
325502

说明

第一组样例解释：

符合题意的(i,j)(i,j)有2020对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
i=1  j=3  i^j=2
i=1  j=5  i^j=4
i=1  j=7  i^j=6
i=1  j=9  i^j=8
i=2  j=6  i^j=4
i=2  j=7  i^j=5
i=2  j=10  i^j=8
i=3  j=1  i^j=2
i=3  j=6  i^j=5
i=3  j=7  i^j=4
i=3  j=10  i^j=9
i=5  j=1  i^j=4
i=6  j=2  i^j=4
i=6  j=3  i^j=5
i=7  j=1  i^j=6
i=7  j=2  i^j=5
i=7  j=3  i^j=4
i=9  j=1  i^j=8
i=10  j=2  i^j=8
i=10  j=3  i^j=9

对于27%的数据，$T\le 5, n \le 1000$

对于54%的数据，$T\le 20, n \le 5 \times 10^5$

对于90%的数据，$T\le 10^5, n \le 10^{18}$

最后一个点，$T=3\times 10^6 \ ,\ n\le 10^{18}$

题解

写个暴力。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
int n , t , ans;
const int mod = (int)1e9+7;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans = 0;
		scanf("%d",&n);
		for(int i = 1 ; i <= n ; ++i)
			for(int j = 1 ; j <= n ; ++j)
			{
				int x = i ^ j;
				if(x >= std::min(i , j) && x <= std::max(i , j)) 
				   	++ans;
				if(ans > mod) ans -= mod;
			}
		printf("%d\n",ans);
	}

}

然后挖掘下性质。