没什么好说的……
# 题面
> 洛谷 - T1
> 洛谷 - T2
> 洛谷 - T3
# 解析
T1 太 naive 了……为什么会在提高组里面
T2. 魔法值
首先有一个非常暴力的想法：暴力转移，记 $f_{i,t}$ 表示城市 $i$ 在第 $t$ 天的时候具有的魔法值，就暴力从 $i-1$ 天转移到第 $i$ 天就行了。
然后非常显然的，因为图并没有变化，每一次转移的形式其实是一样的。于是乎可以写出一个转移矩阵 $M$：$M_{i,j}$ 是一个 01 值，则
可以看到 $M_{u,v}$ 其实就是表示 $u,v$ 之间是否有边（邻接矩阵）。因为图不会变，$M$ 肯定是不会变的。
于是可以想到倍增（似乎不能称之为矩阵快速幂，因为转移的时候并不是矩阵乘法）。定义 $M_i$ 为一个矩阵，表示从第 $t$ 天转移到 $t+2^i$ 天的转移矩阵。$M_0$ 也就是原图中的邻接矩阵，然后我们可以 $O(n^3\times 32)$（32是log的结果）预处理出 $M_i$。
接下来就产生了两种不一样的处理方法（实际上有一种是卡过去的）：
对于每个询问，设询问求的是第 $t$ 天的结果，那么我们要求出转移 $t$ 天的转移矩阵。于是初始化一个矩阵 $N$，$N$ 只有对角线上为 $1$。再枚举倍增，如果 $t$ 在二进制下第 $i$ 位为 $1$，则将 $N$ 和 $M_i$ 转移一下，得到新的 $N$。
最后就得到了第 $t$ 天的转移矩阵。复杂度 $O(qn^3\times 32)$？似乎有一点大……但是因为是 01 矩阵，可以用 bitset 优化一下，也能卡过。
方法 1 中我们处理了所有城市的转移方式，但是我们只需要城市 $1$ 的转移方式，所以可以只初始化一个 $n\times 1$ 的矩阵 $N$，其中 $N_{1,1}=1$，表示城市 $1$ 的转移方式，照样可以倍增转移，而且这样就少了一个 $O(n)$ 的复杂度。
这样已经可以AC了，再加上 bitset 的优化就会跑的飞快。
T3. 优秀子序列
把 $n$ 个数看成二进制下的 $n$ 个集合，于是题目的意思就变成了“将若干个不相交的集合 $S_i$ 并起来得到 $T$（一个二进制数），价值为 $\phi(T+1)$，求价值之和”。
注意到 $n$ 比值域大，那么我们先记录每个值出现的次数 $cnt_i$，然后枚举值域大小肯定比枚举 $n$ 快。
这就让我们想到了一个子集DP，最初是一个空集，然后我们往里面加入（求并）一些集合，要求这些集合不能有交。也就是定义 $f_S$ 表示得到的集合为 $S$ 的方案数，转移也比较简单：
Note. 下面的 $U$ 表示的是全集，二进制下最大就是 $2^{18}-1$，代表了一个大小为 $18$ 的集合。
先从 1 到 $U$ 枚举 $S$，表示我们要向现有的集合 $T$ 中插入集合 $S$；然后枚举现有的集合 $T$，要求 $T$ 不能与 $S$ 有交，即 $T\subseteq\complement_US$（$S$ 的补集），于是可以用枚举子集的方法枚举 $T$。
那么转移就非常简单：$f’_{S\cup T}=f_{S\cup T}+cnt_S\times f_T$。
这样做的复杂度？需要用到枚举子集的一个非常重要的性质：
枚举一个大小为 $n$ 的集合的每个子集 $S$，再枚举 $S$ 的所有子集；复杂度为 $O(3^n)$。
不难发现 DP 转移的枚举方式就是性质中所描述的，因此是 $O(3^n)$。但是 $3^{18}$ 仍然非常大，考虑尽量剪枝：
- $cnt_S=0$ 肯定直接跳过这个 $S$（这样 70pt 就有了）。
- 因为我们从小到大枚举 $S$，那么设 $S$ 在二进制下最高位为 $i$，则转移时，如果 $T$ 的最高位大于 $i$，那此时 $f_T=0$，就没有必要枚举。
# 源代码
T2 (1).cpp：非常规做法（卡时间）
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
|
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m,cas;
bitset<N> tra[35][N],cur[N],tmp;
long long org[N];
inline int Ri(){
register int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
return a;
}
int main(){
n=Ri(),m=Ri(),cas=Ri();
for(int i=0;i<n;i++) scanf("%lld",&org[i]);
for(int i=1;i<=m;i++){
int u=Ri(),v=Ri();u--,v--;
tra[0][u].set(v,1),tra[0][v].set(u,1);
}
for(int p=0;p<=32;p++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(tra[p][i].test(j))
tra[p+1][i]^=tra[p][j];
for(int i=1;i<=cas;i++){
long long tim;scanf("%lld",&tim);
for(int j=0;j<n;j++)
cur[j]=0,cur[j].set(j,1);
for(int j=32;j>=0;j--)
if(tim>>j&1)
for(int p=0;p<n;p++){
tmp=0;
for(int q=0;q<n;q++)
if(cur[p].test(q))
tmp^=tra[j][q];
cur[p]=tmp;
}
long long ans=0;
for(int j=0;j<n;j++)
if(cur[0].test(j))
ans^=org[j];
printf("%lld\n",ans);
}
return 0;
}
|
T2 (2).cpp：非常 nice 的正解做法
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
|
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100;
int n,m,q;
bitset<N> rel[35][N],rem,tmp;
long long org[N];
inline long long Ri(){
register long long a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
return a;
}
int main(){
n=Ri(),m=Ri(),q=Ri();
for(int i=0;i<n;i++) org[i]=Ri();
for(int i=0;i<m;i++){
int u=Ri()-1,v=Ri()-1;
rel[0][u].set(v,1);
rel[0][v].set(u,1);
}
for(int i=1;i<35;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
if(rel[i-1][j].test(k))
rel[i][j]^=rel[i-1][k];
while(q--){
long long tim=Ri();
rem=1;
for(int i=0;i<35;i++)
if(tim>>i&1){
tmp=0;
for(int j=0;j<n;j++)
if(rem.test(j))
tmp^=rel[i][j];
rem=tmp;
}
long long ans=0;
for(int i=0;i<n;i++)
if(rem.test(i))
ans^=org[i];
printf("%lld\n",ans);
}
return 0;
}
|
T3.cpp
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+10,N=1<<18,MOD=1e9+7;
int n,nprn;
int cnt[N],f[N],phi[N+1],prn[N];
bool vis[N];
inline int Ri(){
register int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
return a;
}
void Init(){
phi[0]=phi[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]) phi[i]=i-1,prn[++nprn]=i;
for(int j=1;j<=nprn && prn[j]*i<=N;j++){
int x=prn[j]*i;
vis[x]=true;
if(i%prn[j]) phi[x]=1ll*phi[i]*(prn[j]-1)%MOD;
else{
phi[x]=1ll*phi[i]*prn[j]%MOD;
break;
}
}
}
}
int main(){
Init();
n=Ri();
int mx=0,ans=1;
f[0]=1;
for(int i=0,thi;i<n;i++){
cnt[thi=Ri()]++;
mx=max(mx,thi);
}
int lim=0;
for(register int S=1;S<N;S++){
if(S>(1<<lim)) lim++;
if(cnt[S]){
int T=(N-1)^S;
for(register int i=17;i>lim;i--)
if(T>>i&1)
T^=(1<<i);
for(register int i=T;i;i=(i-1)&T){
f[i|S]+=1ll*cnt[S]*f[i]%MOD;
if(f[i|S]>=MOD) f[i|S]-=MOD;
}
f[S]+=cnt[S];
if(f[S]>=MOD) f[S]-=MOD;
}
if(f[S]){
ans+=1ll*f[S]*phi[S+1]%MOD;
if(ans>=MOD) ans-=MOD;
}
}
while(cnt[0]--) ans=(ans<<1)>=MOD? (ans<<1)-MOD:(ans<<1);
printf("%d\n",ans);
return 0;
}
|
THE END
Thanks for reading!