[KMOI R1] 集合 First 题解

· · 题解

\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;
}