自动搬运

查看原文

来自洛谷，原作者为

	Fire_flame 乐观乐观再乐观

搬运于2025-08-24 22:51:02，当前版本为作者最后更新于2023-05-06 22:03:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathbf{Solution}$

$\mathtt{15}$ 分做法

写一个 dfs 暴力，可以拿到 $\mathtt{15}$ 分的好成绩。

$\mathtt{25}$ 分做法

不知道，期待比赛时有人拿到。

$\mathtt{100}$ 分做法

我们考虑构造，令 $m=2^{n-1}$。

将 $A=\{1,2,3\dots,n\}$ 的子集分成两组 $Q_i,T_i(1\le i\le m)$，且满足 $n\in T_i,n\notin Q_i$，集合 $T_i$ 里面去掉 $n$ 之后等于 $Q_i$。

所以 $G(Q_i)=\sum\limits_{j=1}^{|Q_i|}Q_{i,j}\times(-1)^{j+1}=Q_{i,1}-Q_{i,2}+\dots$

$G(T_i)=\sum\limits_{j=1}^{|T_i|}T_{i,j}\times(-1)^{j+1}=T_{i,1}-T_{i,2}+T_{i,3}-\dots=n-Q_{i,1}+Q_{i,2}-\dots$

那么 $G(Q_i)+G(T_i)=n$。

故答案为 $n\times m=n\times 2 ^{n-1}$，时间复杂度 $O(\log n)$。

$\mathtt{55}$ 分做法

因为模数是 $911451407$，大约是 $9\times10^8$，所以在用快速幂求完 $m$ 之后要用龟速乘乘上 $n$，不然 $9\times10^8\times10^{16}>10^{18}$ 会爆 long long。

没有用龟速乘或者提前取模 $\mathtt{55}$ 分。

标程：

#include<bits/stdc++.h>//by Fire_flame
#define int long long
using namespace std;
const int MOD = 911451407;
int n;
int fpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1)res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
int ftime(int a, int b){
	int res = 0;
	while(b){
		if(b & 1)res = (res + a) % MOD;
		a = (a + a) % MOD;
		b >>= 1;
	}
	return res;
}
signed main(){
	scanf("%lld", &n);
	printf("%lld", ftime(fpow(2, n - 1), n));
	return 0;
}

标程二：

#include<bits/stdc++.h>//代码提供者：OI_LOSER_CGY
#define int long long
using namespace std;
int n,mod=911451407; 
signed main(){
	scanf("%lld",&n);
	int res=n%mod,a=2;n--;
	while(n){
		if(n%2)res=res*a%mod;
		a=a*a%mod,n/=2;
	}
	printf("%lld\n",res);
	return 0;
}