CF1034E Little C Loves 3 III

好巧妙的构造!

CF1034E Little C Loves 3 III

一句话题意:求两个数组的子集卷积,模 4 ,n21n \le 21

首先,我们显然会 O(n22n)O(n^22^n) 的裸的子集卷积,在这里可以看到。但是显然不足以通过本题。

这里就要用上出题人的神仙构造了,令模数为 pp ,设

ai=aippopcount(i)a'_i = a_i p^{popcount(i)}

然后考虑将这样变换后的 a,ba,b 搞个或卷积,算出来是:

[x](a×orb)=jk=xajbkppopcount(j)+popcount(k)[x](a' \times_{or} b') = \sum_{j|k = x} a_jb_k p^{popcount(j)+popcount(k)}

我们考虑,如果 jk=x,j&k=0j|k=x,j\&k = 0 那么有 popcount(j)+popcount(k)=popcount(x)popcount(j)+popcount(k) = popcount(x) ,如果 jk=x,j&k0j|k=x,j\& k \neq 0 那么有 popcount(j)+popcount(k)>popcount(x)popcount(j) + popcount(k) > popcount(x) 。设 c=a×bc' = a'\times b' ,那么我们就有最终答案 c[x]=c[x]ppopcount(x)c[x] = \frac{c'[x]}{p^{popcount(x)}} 。为什么呢?只有 ij=x,i&j=0i|j=x,i\&j = 0 的时候 ajbka_jb_kc[x]c[x] 才有贡献,如果 ij=x,i&j0i|j=x,i\&j\neq 0 那么卷积的时候算出来的一定是个 pp 的倍数,就直接爆零了。。

这做法是有局限性的。显然计算过程中不能模 pp 。。但是这题 pp 只有 4 啊,aippopcounta_ip^{popcount}最大也不会过 4224^{22} ,然后卷起来也不可能炸出 __int128 的范围。。

但是这题不知道为啥开 long long 就过去了。。不是很懂。。反正 CF 写 int128 挺麻烦的。。就不管了吧(雾

#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 int long long
#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() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
\