T20200903赛后总结(转载)

Posted on Edited on In Word count in article: 1.8k Reading time ≈ 7 mins.
大东辰的测试

特别鸣谢：DeNeRATe

总结

这次是真的全考数学了/kk

死磕T1，结果自我感觉最难的就是T1了。。。

最后直接雪崩。。。

T20200903-1.gif

T1

算法

构造

题目

T20200903-A.png

分析

我们先考虑弱化版：

\[ Ans = \sum^{n}_{i=1} \sum^{n}_{j=i+1} \sum^{n}_{k=j+1} (A_i \bigoplus A_j) \times (A_j \bigoplus A_k) \] 发现，非常简单，化简一下 \[ Ans = \sum^{n}_{j=1} \sum^{j-1}_{i=1} \sum^{n}_{k=j+1} (A_i \bigoplus A_j) \times (A_j \bigoplus A_k) \\ =\sum^{n}_{j=1} \left( \sum^{j-1}_{i=1} A_i \bigoplus A_j \right) \times \left( \sum^{n}_{k=j+1} A_j \bigoplus A_k \right) \] 我们令 \[ L[j] = \sum^{j-1}_{i=1} A_i \bigoplus A_j \\ R[j] = \sum^{n}_{k=j+1} A_j \bigoplus A_k \] 所以我们可以得到 \[ Ans = \sum^{n}_{j=1} L[j] \times R[j] \] 我们进而化简

设，$ Bit(i,j) \(表示\)i\(的第\)j\(位是\) 1/0 $ \[ L[j] = \sum^{30}_{k=0} 2^k \times \sum^{j-1}_{i=0} [Bit(A_j,k) \neq Bit(A_i,k)] \\ R[j] = \sum^{30}_{k=0} 2^k \times \sum^{n}_{i=j+1} [Bit(A_j,k) \neq Bit(A_i,k)] \]

有了上边的基础

对于升级版

我们就可以轻松切了

（当时推到这儿了，结果还是没有维护出来。。。wtcl） \[ Ans = \sum_{i<j<k} (A_i \bigoplus A_j) \times (A_j \bigoplus A_k) \times (A_i \bigoplus A_k) \\ = \sum_{i<j<k} (A_i \bigoplus A_j) \times (A_j \bigoplus A_k) \times \sum^{30}_{b=0} 2^b \times (Bit(A_i,b) \neq Bit(A_k,b)) \\ = \sum^{30}_{b=0} 2^b \times \sum_{i<j<K} (A_i \bigoplus A_j) \times (A_j \bigoplus A_k) \times (Bit(A_i,b) \neq Bit(A_k,b)) \] 所以，我们只需要枚举$ Bit(A_i,b) Bit(A_k,b) $时的每一位即可统计答案

代码

吐槽一下：实现是真的闹心。。。

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
67
68
69
70
71
72
73
74
75
76
//xor 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

#define LL long long
#define INF 0x7fffffff
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define MOD 998244353
using namespace std;
const LL MAXN=2e5+10,Limit=35;

LL Total,Num[MAXN],Ans;
LL L[MAXN][2],R[MAXN][2];
LL Suf[Limit][2][2],Pre[Limit][2][2];
LL Two[Limit]={1};

inline void File() {
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
}

inline LL Solve(LL Temp) {
	Cl(Suf,0);
	FOR(i,1,Total) {
		L[i][0]=0;
		L[i][1]=0;
		FOR(j,0,30) {
			LL Loc=((Num[i] & (1<<j))>0);
			(L[i][0]+=Suf[j][Loc ^ 1][0])%=MOD;
			(L[i][1]+=Suf[j][Loc ^ 1][1])%=MOD;
		}
		LL Bit=((Num[i] & (1<<Temp))>0);
		FOR(j,0,30) {
			LL Loc=((Num[i] & (1<<j))>0);
			(Suf[j][Loc][Bit]+=Two[j])%=MOD;
		}
	}
	Cl(Pre,0);
	BOR(i,Total,1) {
		R[i][0]=0;
		R[i][1]=0;
		FOR(j,0,30) {
			LL Loc=((Num[i] & (1<<j))>0);
			(R[i][0]+=Pre[j][Loc ^ 1][0])%=MOD;
			(R[i][1]+=Pre[j][Loc ^ 1][1])%=MOD;
		}
		LL Bit=((Num[i] & (1<<Temp))>0);
		FOR(j,0,30) {
			LL Loc=((Num[i] & (1<<j))>0);
			(Pre[j][Loc][Bit]+=Two[j])%=MOD;
		}
	}
	LL Res=0;
	FOR(i,1,Total) {
		LL Val=(L[i][0]*R[i][1]+L[i][1]*R[i][0])%MOD;
		(Res+=(Val*Two[Temp]))%=MOD;
	}
	return Res%MOD;
}

int main() {
	File();
	scanf("%lld",&Total);
	FOR(i,1,30) Two[i]=Two[i-1]*2%MOD;
	FOR(i,1,Total) scanf("%lld",&Num[i]);
	FOR(Loc,0,30) (Ans+=Solve(Loc))%=MOD;
	printf("%lld\n",Ans%MOD);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2

算法

动态规划+构造

题目

T20200903-B.png

分析

吐槽一下：由于我把题读错了？导致对着题解搞了好久

我们如果直接枚举\(n,k\)状态，那么算重是一定的了

所以，我们需要枚举每一个数选的个数

自然，我们就可以设计出状态DP[i][j]表示选了\(i\)个数，总和位\(j\)的集合数

所以我们可以先求出DP[i][j]，最后来枚举每一个数的个数即可

但我们不能像通常一样枚举\(i,j\)，这样是$ O(n^3) $

我们可以考虑两种转移方式：

  • 在当前集合状态下加一个1
  • 将当前集合中的所有数加1

所以，我们的转移就是$ O(n^2) $了

代码

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
//set
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x7fffffff
#define MOD 1000000007
using namespace std;
const LL MAXN=5e3+10;

LL DP[MAXN][MAXN],Ans;
LL Total,Base,Limit;

inline void File() {
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
}

inline LL Fast(LL A,LL B) {
	LL Res=1;
	while(B) {
		if(B & 1) { Res=(Res*A)%MOD; }
		A=(A*A)%MOD; B>>=1;
	} 
	return Res%MOD;
}

int main() {
    File();
	scanf("%lld %lld %lld",&Total,&Limit,&Base);
	DP[0][0]=1;
	FOR(i,0,Limit-1) 
		FOR(j,0,Total) {
			(DP[i+1][j+1]+=DP[i][j])%=MOD;
			if(i && j+i<=Total) (DP[i][j+i]+=DP[i][j])%=MOD;
		}
	FOR(i,1,Total) {
		LL Sum=0;
		for(LL j=1;j<=(Total/i) && j<=Limit;j++) 
			(Sum+=DP[Limit-j][Total-i*j])%=MOD;
		(Ans+=Sum*Fast(i,Base))%=MOD;
	}
	printf("%lld\n",Ans%MOD);
    fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}

T3

算法

组合数学+构造

题目

T20200903-C.png

分析

因为我们直接正面解决问题是很困难的

所以我们考虑计算无法满足题目要求的集合的个数，即：

  • 最大值不超过\(k\)
  • 所有数异或之和位0

引理

从高到低考虑，一定存在一个\(A_i\)满足$ Bit(A_i,j) Bit(k,j) $

证明显然，故咕

因为$ i ,A_i k $

所以当存在时，当且仅当\(A_i\)的第\(j\)位为0

有了这个引理，这道题基本就可以宣告结束了

对于剩下的\(n-1\)个数，他们的剩下\(j-1\)位可以乱填都是没有问题的

所以我们来考虑$ Bit(A_i,j)==0 \(，他的\) [0,j-1] \(有\) 2^j $种情况

对于$ Bit(A_i,j)==1 \(，他的\) [0,j-1] \(有\) k ,,, & ,,, (2^j-1)+1 $

所以，我们可以枚举满足$ Bit(A_i,j)==0 $的数的个数

方案数为： \[ {n \choose v} \times (2^j)^{v-1} \times (k \,\,\, \& \,\,\, (2^j-1)+1)^{n-v} \] 我们必须要保证\(v\)和\(n\)的奇偶性相同，才能使得最后异或和为0

进而，我们可以通过二项式定理来化简

对于\(n\)为偶数的情况（奇数很简单的啦） \[ Ans = (2^{-j-1}) \times \sum^{n}_{n=2} {n \choose v} \times (2^j)^v \times (k \,\,\, \& \,\,\, (2^j-1)+1)^{n-v} \times ((-1)^v + 1^v) \] 所以 \[ (2^{-j-1}) \times \sum^{n}_{v=2} {n \choose v} \times (2^j)^v \times (k \,\,\, \& \,\,\, (2^j-1)+1)^{n-v} \times (-1)^v \\ \Rightarrow (2^{-j-1}) \times ((k \,\,\, \& \,\,\, (2^j-1)+1-2^j)^n - (k \,\,\, \& \,\,\, (2^j-1)+1)^n) \\ (2^{-j-1}) \times \sum^{n}_{v=2} {n \choose v} \times (2^j)^v \times (k \,\,\, \& \,\,\, (2^j-1)+1)^{n-v} \times 1^v \\ \Rightarrow (2^{-j-1}) \times ((k \,\,\, \& \,\,\, (2^j-1)+1+2^j)^n - (k \,\,\, \& \,\,\, (2^j-1)+1)^n) \] 时间复杂度：$ O(log^2n) $

期望得分：100分

代码

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
//xor2 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define LL long long
#define MOD 998244353
#define FOR(i,A,B) for(LL i=A;i<=B;i++) 
#define BOR(i,A,B) for(LL i=A;i>=B;i--) 
#define Cl(X,Y) memset((X),(Y),sizeof(X))
using namespace std;

LL Total,Ans,Limit,Temp;

inline void File() {
	freopen("xor2.in","r",stdin);
	freopen("xor2.out","w",stdout);
}

inline LL Fast(LL A,LL B) {
	LL Res=1;
	A=((A%MOD+MOD)%MOD);
	while(B) {
		if(B & 1) Res=(Res*A)%MOD;
		A=(A*A)%MOD; B>>=1;
	} 
	return Res%MOD;
}

int main() {
	File();
	scanf("%lld %lld",&Total,&Limit);
	if(!(Total%2)) Temp++;
	BOR(i,29,0) {
		if(Limit & (1<<i)) {
			LL Last=(Limit & ((1<<i)-1))+1;
			LL Val=(1<<i);
			if(Total%2==0) {
				Ans=Fast(Last+Val,Total)%MOD;
				(Ans+=Fast(Last-Val,Total))%=MOD;
				(Ans*=((MOD+1)/2))%=MOD;
				Ans=((Ans-Fast(Last,Total))%MOD+MOD)%MOD;
				(Temp+=(Ans*Fast(Val,MOD-2)))%=MOD;
			} else {
				Ans=Fast(Last+Val,Total)%MOD;
				Ans=((Ans-Fast(Last-Val,Total))%MOD+MOD)%MOD;
				(Ans*=((MOD+1)/2))%=MOD;
				(Temp+=Ans*Fast(Val,MOD-2)%MOD)%=MOD;
			}
			if(Total & 1)break;
		}
	}
	printf("%lld\n",((Fast(Limit+1,Total)-Temp)%MOD+MOD)%MOD);
	fclose(stdin);
	fclose(stdout);
	return 0;
}