C++(clang++ 11.0.1) 解法, 执行用时: 80ms, 内存消耗: 5112K, 提交时间: 2022-08-06 19:40:35
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define int ll
int ty[20];
template <class T>
void fwt(T f[],T g[],int ldn)
{
int n=(1<<ldn);
for(int ldm=1;ldm<=ldn;ldm++)
{
int m=(1<<ldm),mh=m>>1;
for(int r=0;r<n;r+=m)
{
int t1=r,t2=r+mh;
for(int j=0;j<mh;j++,t1++,t2++)
{
T u=f[t1],v=f[t2],x=g[t1],y=g[t2];
if(ty[ldm]==0){f[t1]+=f[t2];g[t1]+=g[t2];f[t2]=g[t2]=0;}
else if(ty[ldm]==1){f[t1]+=f[t2];g[t1]+=g[t2];}
else if(ty[ldm]==2){f[t1]+=f[t2];swap(g[t1],g[t2]);g[t1]+=g[t2];}
else if(ty[ldm]==3)g[t1]=g[t2]=x+y;
else if(ty[ldm]==4){swap(f[t1],f[t2]);f[t1]+=f[t2];g[t1]+=g[t2];}
else if(ty[ldm]==5)f[t1]=f[t2]=u+v;
else if(ty[ldm]==6){f[t1]=u+v;f[t2]=u-v;g[t1]=x+y;g[t2]=x-y;}
else if(ty[ldm]==7){f[t2]+=f[t1];g[t2]+=g[t1];}
else if(ty[ldm]==8){swap(f[t1],f[t2]);swap(g[t1],g[t2]);f[t1]+=f[t2];g[t1]+=g[t2];}
else if(ty[ldm]==9){f[t1]=u-v;f[t2]=u+v;g[t1]=x-y;g[t2]=x+y;}
else if(ty[ldm]==10){f[t1]=f[t2]=u+v;swap(g[t1],g[t2]);}
else if(ty[ldm]==11){swap(g[t1],g[t2]);f[t2]+=f[t1];g[t2]+=g[t1];}
else if(ty[ldm]==12){swap(f[t1],f[t2]);g[t1]=g[t2]=x+y;}
else if(ty[ldm]==13){swap(f[t1],f[t2]);f[t2]+=f[t1];g[t2]+=g[t1];}
else if(ty[ldm]==14){swap(f[t1],f[t2]);swap(g[t1],g[t2]);f[t2]+=f[t1];g[t2]+=g[t1];}
else if(ty[ldm]==15){f[t2]+=f[t1];g[t2]+=g[t1];f[t1]=g[t1]=0;}
}
}
}
}
template <class T>
void ifwt(T f[],int ldn)
{
int n=(1<<ldn);
for(int ldm=1;ldm<=ldn;ldm++)
{
int m=(1<<ldm),mh=m>>1;
for(int r=0;r<n;r+=m)
{
int t1=r,t2=r+mh;
for(int j=0;j<mh;j++,t1++,t2++)
{
T u=f[t1],v=f[t2];
if(ty[ldm]==0);
else if(ty[ldm]==1)f[t1]-=f[t2];
else if(ty[ldm]==2)f[t1]-=f[t2];
else if(ty[ldm]==3);
else if(ty[ldm]==4)f[t1]-=f[t2];
else if(ty[ldm]==5);
else if(ty[ldm]==6){f[t1]=(u+v)>>1;f[t2]=(u-v)>>1;}
else if(ty[ldm]==7)f[t2]-=f[t1];
else if(ty[ldm]==8)f[t1]-=f[t2];
else if(ty[ldm]==9){f[t1]=(v-u)>>1;f[t2]=(u+v)>>1;}
else if(ty[ldm]==10);
else if(ty[ldm]==11)f[t2]-=f[t1];
else if(ty[ldm]==12);
else if(ty[ldm]==13)f[t2]-=f[t1];
else if(ty[ldm]==14)f[t2]-=f[t1];
else if(ty[ldm]==15)continue;
}
}
}
}
// will **change** f[] and g[], result is stored in f[]
template <class T>
void convolution(T f[],T g[],int n)
{
int ldn=__lg(n);assert((1<<ldn)==n);
fwt(f,g,ldn);
for(int i=0;i<n;i++)f[i]=f[i]*g[i];
ifwt(f,ldn);
}
char s[10];
ll f[300005],g[300005];
void solve()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=4;j++)
{
if(s[j]=='1')(ty[i]<<=1)|=1;
else ty[i]<<=1;
}
}
for(int i=0;i<(1<<n);i++)scanf("%lld",&f[i]);
for(int i=0;i<(1<<n);i++)scanf("%lld",&g[i]);
convolution(f,g,(1<<n));
for(int i=0;i<(1<<n);i++)printf("%lld%c",f[i]," \n"[i==(1<<n)-1]);
}
signed main()
{
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// int _;scanf("%lld",&_);while(_--)
solve();
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 776ms, 内存消耗: 5204K, 提交时间: 2022-11-02 00:12:12
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
constexpr int maxn = 18;
ll a[1<<maxn], b[1<<maxn];
vector<string>func;
pll A(string s, ll x, ll y){
if(s=="0000") return {x+y, 0};
if(s=="0001") return {x+y, y};
if(s=="0010") return {x+y, y};
if(s=="0011") return {x, y};
if(s=="0100") return {x+y, x};
if(s=="0101") return {x+y, x+y};
if(s=="0110") return {x+y, x-y};
if(s=="0111") return {x, x+y};
if(s=="1000") return {x+y, x};
if(s=="1001") return {x+y, x-y};
if(s=="1010") return {x+y, x+y};
if(s=="1011") return {x, x+y};
if(s=="1100") return {y, x};
if(s=="1101") return {y, x+y};
if(s=="1110") return {y, x+y};
if(s=="1111") return {0, x+y};
return {0,0};
}
pll B(string s, ll x, ll y){
if(s=="0000") return {x+y, 0};
if(s=="0001") return {x+y, y};
if(s=="0010") return {x+y, x};
if(s=="0011") return {x+y, x+y};
if(s=="0100") return {x+y, y};
if(s=="0101") return {x, y};
if(s=="0110") return {x+y, x-y};
if(s=="0111") return {x, x+y};
if(s=="1000") return {x+y, x};
if(s=="1001") return {x+y, x-y};
if(s=="1010") return {y, x};
if(s=="1011") return {y, x+y};
if(s=="1100") return {x+y, x+y};
if(s=="1101") return {x, x+y};
if(s=="1110") return {y, x+y};
if(s=="1111") return {0, x+y};
return {0,0};
}
pll inv_C(string s, ll x, ll y){
if(s=="0000") return {x, y};
if(s=="0001") return {x-y, y};
if(s=="0010") return {x-y, y};
if(s=="0011") return {x, y};
if(s=="0100") return {x-y, y};
if(s=="0101") return {x, y};
if(s=="0110") return {(x+y)/2, (x-y)/2};
if(s=="0111") return {x, y-x};
if(s=="1000") return {x-y, y};
if(s=="1001") return {(x-y)/2, (x+y)/2};
if(s=="1010") return {x, y};
if(s=="1011") return {x, y-x};
if(s=="1100") return {x, y};
if(s=="1101") return {x, y-x};
if(s=="1110") return {x, y-x};
if(s=="1111") return {x, y};
return {0,0};
}
void fwht(ll f[], int n, pll (*trans)(string s, ll x, ll y)){
int len = 1<<n;
for(int bit = 0, step = 1; step < len ; bit++, step *= 2){
for(int i = 0 ; i < len ; i += step*2){
for(int j = i ; j < i + step ; j ++){
auto x = f[j], y = f[j+step];
tie(f[j], f[j+step]) = trans(func[bit], x, y);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
func.resize(n);
for(int i = 0 ; i < n ; i ++) cin >> func[i];
for(int i = 0 ; i < (1<<n) ; i ++) cin >> a[i];
for(int i = 0 ; i < (1<<n) ; i ++) cin >> b[i];
fwht(a, n, A), fwht(b, n, B);
for(int i = 0 ; i < (1<<n) ; i ++) a[i] *= b[i];
fwht(a, n, inv_C);
for(int i = 0 ; i < (1<<n) ; i ++) cout << a[i] << " \n"[i==(1<<n)-1];
return 0;
}
和 
个整数 )
，它们可以等于 
或 
(
, 
, 
)。
之间（包括
和 
。令 
和 
为它们的二进制表示 (
)。定义 %20%3D%20%5Csum%5Climits_%7Bi%20%3D%200%7D%5E%7Bn%20-%201%7D%7Bc(i%2C%20x_i%2C%20y_i)%5Ccdot%202%5Ei%7D)
。显然，)
也是 
和 
，对于所有)
， 找到)
的值的多重集，其中
。。
位二进制字符串。第
个字符串由
、
、
、
以这个特定的顺序的值组成。
个整数
组成，表示多重集中数字
的数量（
，
）。多重集中没有其他数字。