Reincarnation

正因为梦易碎，才格外美好。

CF1034E Little C Loves 3 III

发表于 更新于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

卡常毒瘤多项式。

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1034/E

形式化题意：给定两个长度为 的序列 ，求序列 满足：

对 取模。 以字符串形式输出。

数据范围：

时空限制：

一眼 板子，结果交上去一发 ，然后发现了奇妙的时空限制和数据范围，意识到 大概是过不了的，我们需要挖掘题目性质。

注意到模数十分特殊，为 ，将值域限制在了一个很小很小的部分。

想起不知道是在多久，似乎在 里做过一道题，大概是要通过压位进行哈希，并通过随机种子将数列还原来把时空压到一个很小很小的部分，或许这也是我们需要的。

在普通的子集卷积中，我们需要一个二维的状态 ，而 与 本身应当是一一对应（答案）的，但我们的转移确实 的。

由于 ，那其 就只有 三种取值，我们是否可以通过一些奇妙的方式来优化掉 呢，当然是可以的。如果能够优化掉 位，我们就可以将其转化为 ，从而在 内解决。

而 和 最本质的区别，就是条件 。

容易发现，对于条件 ，实则是满足 ，这个性质有什么用吗？当 时，一定存在 ，这是显然的，那我们忽略掉这个条件，但又要使得这个部分对答案不贡献。

注意到取模 这个特殊性质，我们令 ，再使得 。那 之间有什么关系呢？

当 时，并不能被计入答案，而此时也满足 ，转换为指数，就会有 ，也就是：

而当最后我们对答案进行取模 时，这一部分就不会产生贡献。那对于 的情况，也就是 ，所以我们得出结论：，而如果有取模情况，那就属于自然取模溢出了。

然后卡常，要开 long long，但不要多开，否则爆空间。由于是字符串形式输入，而 scanf 会超时间，建议用改良了的快读。

AC Code
 
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
77
78
79
80
81
82
83
84
// ----- Eternally question-----
// Problem: Little C Loves 3 III
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1034E
// Memory Limit: 62 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-14 16:39:37
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
inline ll read()
{
	// ll x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	return ch+'0';
	// while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	// if(t) x=-x;
	// return x;
}
const int MAXN=3e6+10,MAXS=22;
int N,Tot;
ll a[MAXN],b[MAXN];
int Bit[MAXN];
inline void FWT(ll a[],int inv)
{
	for(int mid=1;mid<Tot;mid<<=1)
		for(int i=0;i<Tot;i+=mid*2)
			for(int j=0;j<mid;++j)
				a[i+j+mid]+=a[i+j]*inv;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);Tot=1<<N;
	for(int i=1;i<Tot;++i) Bit[i]=Bit[i>>1]+(i&1);
	for(int i=0;i<Tot;++i) a[i]=read()<<(Bit[i]<<1);
	for(int i=0;i<Tot;++i) b[i]=read()<<(Bit[i]<<1);
	// for(int i=0;i<=N;++i) FWT(a[i],1),FWT(b[i],1);
	FWT(a,1),FWT(b,1);
	for(int i=0;i<Tot;++i) a[i]*=b[i];
	FWT(a,-1);
	for(int i=0;i<Tot;++i) putchar(((a[i]>>(Bit[i]<<1))&3)+'0');
	return 0;
}
/*

*/
相关文章