title

題目

solution

先說很神仙的結論構造：對于$a_i$，$a_i=v_i?4^{pop\_count(i)}$，$b$同理
$c_i={\sum }_{j|k=i}{a}_i?b_j$，則$an{s}_i\equiv \frac{c_i}{4^{pop\_count(i)}}\mathrm{m}\mathrm{o}\mathrm{d}4$

證明：$pop\_count(i)+pop\_count(j)\ge pop\_count(i|j)$
①$i\&j=0$，對答案將有貢獻
$$\frac{4^{pop\_count(i)}\times 4^{pop\_count(j)}}{4^{pop\_count(i|j)}}=1$$
②$i\&j=0$，模$4$為$0$，無貢獻
$$\frac{4^{pop\_count(i)}\times 4^{pop\_count(j)}}{4^{pop\_count(i|j)}}=4^x,x\in N^{?}$$
構造非常巧妙，一般來說是不可能自己想得出來的；這種結論都是難知道卻好證
o(╥﹏╥)o I’m so vegetable！

code

#include <cstdio> #define int long long #define maxn 2100000 int n, N; int a[maxn], b[maxn], c[maxn];void FWT_or( int *v, int opt ) {for( int i = 1;i < n;i <<= 1 )for( int j = 0;j < n;j += ( i << 1 ) )for( int k = 0;k < i;k ++ )v[j + k + i] += opt * v[j + k]; }signed main() {scanf( "%d", &N );n = 1 << N;for( int i = 0;i < n;i ++ ) scanf( "%1lld", &a[i] );for( int i = 0;i < n;i ++ ) scanf( "%1lld", &b[i] );for( int i = 0;i < n;i ++ ) a[i] <<= ( __builtin_popcount( i ) << 1 );for( int i = 0;i < n;i ++ ) b[i] <<= ( __builtin_popcount( i ) << 1 );FWT_or( a, 1 ), FWT_or( b, 1 );for( int i = 0;i < n;i ++ ) c[i] = a[i] * b[i];FWT_or( c, -1 );for( int i = 0;i < n;i ++ ) c[i] = c[i] >> ( __builtin_popcount( i ) << 1 ) & 3;for( int i = 0;i < n;i ++ ) printf( "%lld", c[i] );return 0; }

總結

以上是生活随笔為你收集整理的CF1034E Little C Loves 3 III（神仙构造+FWT_OR卷积）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。