好巧妙的构造！
CF1034E Little C Loves 3 III
一句话题意：求两个数组的子集卷积，模 4 ，$n \le 21$
首先，我们显然会 $O(n^22^n)$ 的裸的子集卷积，在这里可以看到。但是显然不足以通过本题。
这里就要用上出题人的神仙构造了，令模数为 $p$ ，设
然后考虑将这样变换后的 $a,b$ 搞个或卷积，算出来是：
我们考虑，如果 $j|k=x,j\&k = 0$ 那么有 $popcount(j)+popcount(k) = popcount(x)$ ，如果 $j|k=x,j\& k \neq 0$ 那么有 $popcount(j) + popcount(k) > popcount(x)$ 。设 $c’ = a’\times b’$ ，那么我们就有最终答案 $c[x] = \frac{c’[x]}{p^{popcount(x)}}$ 。为什么呢？只有 $i|j=x,i\&j = 0$ 的时候 $a_jb_k$ 对 $c[x]$ 才有贡献，如果 $i|j=x,i\&j\neq 0$ 那么卷积的时候算出来的一定是个 $p$ 的倍数，就直接爆零了。。
这做法是有局限性的。显然计算过程中不能模 $p$ 。。但是这题 $p$ 只有 4 啊，$a_ip^{popcount}$最大也不会过 $4^{22}$ ，然后卷起来也不可能炸出 __int128 的范围。。
但是这题不知道为啥开 long long 就过去了。。不是很懂。。反正 CF 写 int128 挺麻烦的。。就不管了吧（雾
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
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN ( 1 << 21 ) + 3
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define min( a , b ) ( (a) < (b) ? (a) : (b) )
#define max( a , b ) ( (a) > (b) ? (a) : (b) )
typedef long long ll;
#define __int128 ll
int n;
__int128 a[MAXN] , b[MAXN];
void FWT( __int128* A , int len ) {
for( int mid = 2 ; mid <= len ; mid <<= 1 )
for( int i = 0 ; i < len ; i += mid )
for( int j = i ; j < i + ( mid >> 1 ) ; ++ j )
A[j + ( mid >> 1 )] += A[j];
}
void IFWT( __int128* A , int len ) {
for( int mid = 2 ; mid <= len ; mid <<= 1 )
for( int i = 0 ; i < len ; i += mid )
for( int j = i ; j < i + ( mid >> 1 ) ; ++ j )
A[j + ( mid >> 1 )] -= A[j];
}
ll bit[MAXN];
void solve() {
cin >> n; n = ( 1 << n );
int pr;
rep( i , 0 , n - 1 ) bit[i] = ( 1ll << 2 * __builtin_popcount( i ) );
rep( i , 0 , n - 1 ) scanf("%1d",&pr) , a[i] = pr * bit[i];
rep( i , 0 , n - 1 ) scanf("%1d",&pr) , b[i] = pr * bit[i];
FWT( a , n ) , FWT( b , n );
rep( i , 0 , n - 1 ) a[i] = a[i] * b[i];
IFWT( a , n );
rep( i , 0 , n - 1 ) pr = ( a[i] / bit[i] ) & 3 , printf("%d",pr);
}
signed main() {
solve();
}
|
