关于fwt的一些东西

摘要:
isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(xvoidmaxa(T&x,Ty){if(y>x)x=y;}templatevoidmina(T&x,Ty){if(yvoidread(T&x){intf=1,c;while(c=gc(),c57)if(c=='-')f=-1;x=(c^48);while(c=gc(),c>47&&c>cc)&1]!=a[i1][j1]*b[i1][k1])tt=0;cc++;}}if(!

https://codeforces.ml/gym/102956

这道题是要实现每一位自定义二进制下运算的fwt$A*B=C$ (*是卷积)

跟一般fwt相同,实现过程可以按位进行

考虑构造成$T1A*T2B=T3C$ (*是对应相乘)

将其按照最高位拆开之后,即$A=[A0,A1],B=[B0,B1],C=[C0,C1]$

即要求$T1A(x)*T2B(x)=T3C(x)$

$sum_{i=1}^{2}T1[x][i]*A[i] * sum_{j=1}^{2}T2[x][j]*B[j]=sum_{k=1}^{2}T3[x][k]*C[k]$

所以即要求$T1[x][i]*T2[x][j]=T3[x][k](i otimes j=k)$

所以只需要找到满足的T1,T2,T3即可以实现,另外要保证T3一定是可逆的,即行列式>0

关于fwt的一些东西第1张关于fwt的一些东西第2张
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immintrin.h>
//#include <emmintrin.h>
#include <bits/stdc++.h>
using namespacestd;
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define IL inline
#define rint register intinline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
char ss[1<<24],*A=ss,*B=ss;
IL chargc()
{
    return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void maxa(T &x,T y)
{
    if (y>x) x=y;
}
template<class T>void mina(T &x,T y)
{
    if (y<x) x=y;
}
template<class T>void read(T &x)
{
    int f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
    while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f;
}
const int maxn=1000000;
structcp {
    ll x,y;
    cp operator +(cp B)
    {
        return (cp){x+B.x,y+B.y};
    }
    cp operator -(cp B)
    {
        return (cp){x-B.x,y-B.y};
    }
    ll operator *(cp B)
    {
        return x*B.y-y*B.x;
    }
    int half() { return y < 0 || (y == 0 && x < 0); }
};
ll aa[20][2][2],bb[20][2][2],cc[20][2][2],ah[20][2][2],bh[20][2][2],ch[20][2][2];
char s[30][6];
int h[30],p[30];
voidgao()
{
    rep(i,0,15)
    {
        rep(j,0,81*81*81-1)
        {
            int a[2][2],b[2][2],c[2][2];
            me(a); me(b); me(c);
            int k=j%81;
            rep(i1,0,1)
            {
              rep(j1,0,1)
              {
                  a[i1][j1]=k%3-1;
                  k/=3;
              }
            }
            k=(j/81)%81;
            rep(i1,0,1)
            {
              rep(j1,0,1)
              {
                  b[i1][j1]=k%3-1;
                  k/=3;
              }
            }
            k=(j/81)/81;
            rep(i1,0,1)
            {
              rep(j1,0,1)
              {
                  c[i1][j1]=k%3-1;
                  k/=3;
              }
            }
            bool tt=1;
            rep(i1,0,1)
            {
              int cc=0;
              rep(j1,0,1)
                rep(k1,0,1)
                {
                  if (c[i1][(i>>cc)&1]!=a[i1][j1]*b[i1][k1]) tt=0;
                  cc++;
                } 
            }
            if (!tt) continue;
            int t=c[0][0]*c[1][1]-c[1][0]*c[0][1];
            if(t)
            {
                h[i]=t;
                c[0][1]*=-1; c[1][0]*=-1;
                swap(c[0][0],c[1][1]);
                rep(i1,0,1)
                  rep(j1,0,1)
                  {
                    aa[i][i1][j1]=a[i1][j1];
                    bb[i][i1][j1]=b[i1][j1];
                    cc[i][i1][j1]=c[i1][j1];
                  }
                break;
            }
        }
    }
}
intn,m;
void fwt(ll *a,ll b[20][2][2])
{
    int gg=0;
    for (int i=1;i<m;i*=2,gg++)
      for (int j=0;j<m;j+=(i*2))
        for (int k=0;k<i;k++)
        {
            //cerr<<gg<<" "<<b[gg][0][0]<<" "<<b[gg][0][1]<<" "<<b[gg][1][0]<<" "<<b[gg][1][1]<<endl;
            ll xx=a[j+k],yy=a[i+j+k];
            a[j+k]=b[gg][0][0]*xx+b[gg][0][1]*yy;
            a[i+j+k]=b[gg][1][0]*xx+b[gg][1][1]*yy;
        }
}
const int N=1e6;
ll x[N],y[N];
intmain()
{
   freopen("3.in","r",stdin);
   freopen("3.out","w",stdout);
   ios::sync_with_stdio(false);
   gao();
   cin>>n;
   ll ans=1;
   rep(i,0,n-1)
   {
        cin>>s[i];
        int now=0;
        dep(j,3,0)
          now=now*2+s[i][j]-'0';
        rep(i1,0,1)
       rep(j1,0,1) 
       {
         ah[i][i1][j1]=aa[now][i1][j1];
            bh[i][i1][j1]=bb[now][i1][j1];
            ch[i][i1][j1]=cc[now][i1][j1];
          }
        ans=ans*h[now];
   }
   m=1;
   rep(i,1,n) m=m*2;
   rep(i,0,m-1) cin>>x[i];
   rep(i,0,m-1) cin>>y[i];
   fwt(x,ah); fwt(y,bh);
   rep(i,0,m-1) x[i]=x[i]*y[i];
   fwt(x,ch);
   rep(i,0,m-1) x[i]=x[i]/ans;
   rep(i,0,m-1) cout<<x[i]<<" "; 
   return 0;
}
View Code

https://zerol.me/2019/03/18/CF-102129A/

https://codeforces.com/gym/102129

这题是参考上面那个题解的

egin{eqnarray}
c_0 &=& (a_1+a_2)(b_1+b_2)
c_0 + c_1 + c_2 &=& (a_0 + a_1 + a_2)(b_0 + b_1 + b_2)
c_3 &=& a_2b_2
c_1 + c_3 &=& (a_0 + a_2)(b_0 + b_2)
end{eqnarray}

按照如上化简之后就可以进行4进制下的fwt

关于fwt的一些东西第3张关于fwt的一些东西第4张
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immintrin.h>
//#include <emmintrin.h>
#include <bits/stdc++.h>
using namespacestd;
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define IL inline
#define rint register intinline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
structre{
    inta,b,c;
};
int f(intx)
{
    int k1=0,k2=1;
    while(x)
    {
        int t=x%3;
        x/=3;
        k1+=k2*t;
        k2=k2*4; 
    }
    returnk1;
}
intm1,m2;
const int N=(1<<24)+3;
ll a[N];
intb[N];
void g1(ll &xa,ll &xb,ll &xc,ll &xd)
{
    ll a=xa,b=xb,c=xc,d=xd;
    xa=b+c;
    xb=a+b+c; 
    xc=c;
    xd=a+c;
}
void g11(int &xa,int &xb,int &xc,int &xd)
{
    int a=xa,b=xb,c=xc,d=xd;
    xa=b+c;
    xb=a+b+c; 
    xc=c;
    xd=a+c;
}
void g2(ll &xa,ll &xb,ll &xc,ll &xd)
{
    ll a=xa,b=xb,c=xc,d=xd; 
    xa=a;
    xd=c;
    xb=d-xd;
    xc=b-xa-xb;
}
void fwt(int *a,into)
{
    for (int i=1;i<m2;i*=4)
      for (int j=0;j<m2;j+=(i*4))
        for (int k=0;k<i;k++)
        {
            if (o==0) g11(a[j+k],a[j+k+i],a[j+k+2*i],a[j+k+3*i]);
        }
}
void fwt(ll *a,into)
{
    for (int i=1;i<m2;i*=4)
      for (int j=0;j<m2;j+=(i*4))
        for (int k=0;k<i;k++)
        {
            if (o==0) g1(a[j+k],a[j+k+i],a[j+k+2*i],a[j+k+3*i]);
            else g2(a[j+k],a[j+k+i],a[j+k+2*i],a[j+k+3*i]);
        }
}
intmain()
{
   freopen("3.in","r",stdin);
   freopen("3.out","w",stdout);
   ios::sync_with_stdio(false);
   intn;
   cin>>n;
   m1=1,m2=1;
   rep(i,1,n) m1=m1*3,m2=m2*4;
   rep(i,0,m1-1) { cin>>a[f(i)];} 
   rep(i,0,m1-1) { cin>>b[f(i)];}
   fwt(a,0); fwt(b,0);
   rep(i,0,m2-1) a[i]=a[i]*b[i];
   fwt(a,1);
   rep(i,0,m1-1) cout<<a[f(i)]<<" ";
   return 0;
}
View Code

还有k进制下的fwt

https://www.cnblogs.com/reverymoon/p/10197711.html参考这个博客的

这个矩阵是利用单位根

因为要求$T1[x][i]*T2[x][j]=T3[x][k](i otimes j=k)$

而${w_k}^{xi}*{w_k}^{xj}=w_k^{x(i+j)\%k}$

所以只需要让$T[x][i]={w_k}^{xi}$

egin{bmatrix}
1& 1 & 1& ... & 1\
1& w_k^1& w_k^2& ... & w_k^{k - 1}\
1& w_k^2 & w_k^4& ... & w_k^{2(k - 1)}\
...& ...& ...& ...& ...\
1& w_k^{k - 1}& w_k^{2(k - 1)} & ... & w_k^{(k - 1)(k - 1)}
end{bmatrix}

他的逆矩阵是

$frac{1}{k}$ egin{bmatrix}
1& 1 & 1& ... & 1\
1& w_k^{-1}& w_k^{-2}& ... & w_k^{-(k - 1)}\
1& w_k^{-2} & w_k^{-4}& ... & w_k^{-2(k - 1)}\
...& ...& ...& ...& ...\
1& w_k^{-(k - 1)}& w_k^{-2(k - 1)} & ... & w_k^{-(k - 1)(k - 1)}
end{bmatrix}

这个代码有需要在写。。

免责声明:内容来源于网络,仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Linux quota命令参数及用法详解---Linux磁盘配额限制设置和查看命令微服务架构设计下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

C# 如何提取SaveFileDialog的保存路径

直接使用代码1publicTestOne()2{3InitializeComponent();4SaveFileDialog();//调用打开SaveFileDialog保存对话框5}67#区域保存对话框8privateevoidSaveFileDialog()9{10//startlocalFilePath,fileNameExt,newFileName,...

MIPS学习笔记(一)

本章涉及MIPS变量声明、数据输入和输出、地址获取、分支跳转语句,基本上对应于任何高级语言的最基本操作。该信息的确切形式因汇编程序而异。在MIPS程序集中,标签是后跟冒号的符号名称。)syscall程序的结尾与C类似,可以调用exit函数来停止程序的执行。停止MIPS程序的一种方法是使用类似于在C中调用exit的方法。MIPS中有一个移动指令,它将一个寄存器...

com.aliyun.openservices.shade.com.alibaba.fastjson.JSONException: exepct '[', but {, pos 1, line 1, column 2

错误报告的原因:您放置了一个非List对象,但希望从packagetest中取出List对象;导入java.text。SimpleDateFormat;导入java.util。阵列列表;导入java.util。日期导入java.util。列表importcom.alibaba.fastjson。JSON;导入com.alibaba.fastj...

Google Drive 里的文件下载的方法

Google Drive不提供创建直接下载链接的选项,但您可以通过更改链接形式在本地保存共享内容。例如,通过Google Drive共享的文件链接是:https://drive.google.com/file/d/FILE_ID/edit?usp=sharing如果您将其更改为以下修改版本,然后通过浏览器打开,则将直接下载该文件:https://drive....

seata启动报错的可能原因,以及解决方案

seata启动错误的可能原因及解决方案。首先,我下载了seata 0.9版和jdk 12.0.2版。启动错误的截图是:它显示无法创建虚拟机。我尝试了很多方法,但都没有解决。...

rm 命令(删除文件和目录)

Rm是常用命令。其功能是删除目录中的一个或多个文件或目录。它还可以删除目录及其下的所有文件和子目录。对于链接文件,只删除链接,原始文件保持不变。如果使用rm删除文件,仍然可以将文件恢复到原始状态。yroot@localhosttest1]#Ll总计0[root@localhosttest1]#注意:输入rmlog.log命令后,系统将询问是否删除。输入y后,...