第九集，结束亦是开始

题意：

大致意思就是给你n个3进制的数字，让你计算有多少对数字的哈夫曼距离等于i(0<=i<=2^m)

思路：

这个是一个防ak题，做法是要手推公式的fwt

大概就这个意思

把n个数字标记到大小为3^m的数组里

然后一个简单的方法就是，假设a是标记数组

for i=0 i<3^m i++

for j=0 j<3^m j++

ans[dis(a[i],a[j])]+=a[i]*a[j]

可能i==j的时候被算重复了，大概特判减去一下n就行了

我们发现，如果dis(a[i],a[j])是位运算就好了，这样就直接拍个fwt就行了

然后我们注意到dis(a[i],a[j])其实可以看成是一个三进制的位运算，这时候我们要推一下公式

我们定义一下位运算法则假设符号为*,则i*j=abs(i-j)，且i,j∈[0,2]

给出我当时推导的过程：

a=0+2

b=0-2

c=1

d=0+1+2

C0=(a*a+b*b)/2+c*c

C1=d*d-C0-C2

C2=(a*a-b*b)/2

大概就是把一个长度为n的多项式乘法变成了4个长度为n/3的多项式乘法

0,1,2是卷积前，最高位三进制为0,1,2的三个长度为n/3的多项式

然后我们构造a,b,c,d四个长度为n/3的多项式

C0,C1,C2是卷积后的多项式

这时候我们只需要计算a*a,b*b,c*c,d*d就行了！

至于怎么构造出来a,b,c,d的，可能就看感觉了吧。。。。。。

然后分析一下复杂度

然后就看出来这是一个公比为4/3的等比数列，求和一下就知道T(m)=4^m-3^m

时间复杂度为O(m)=4^m

代码实现

#include<stdio.h>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn = ;

ll pool[/+],*p=pool;

ll ans[];

ll A[maxn];

/*

a=0+2

b=0-2

c=1

d=0+1+2

C0=(a*a+b*b)/2+c*c

C1=d*d-C0-C2

C2=(a*a-b*b)/2

*/

void fwt(ll *A,int len){

    if(len==){

        A[]=A[]*A[];

        return ;

    }

    int nlen=len/;

    ll *a=p;

    p+=nlen;

    ll *b=A;

    ll *c=A+nlen;

    ll *d=A+nlen*;

    for(int i=;i<nlen;i++){

        ll x=A[i],y=A[i+nlen],z=A[i+*nlen];

        a[i]=x+z;

        b[i]=x-z;

        c[i]=y;

        d[i]=x+y+z;

    }

    fwt(a,nlen);fwt(b,nlen);

    fwt(c,nlen);fwt(d,nlen);

    for(int i=;i<nlen;i++){

        ll x=a[i],y=b[i],z=c[i],w=d[i];

        A[i]=(x+y)/+z;

        A[i+nlen*]=(x-y)/;

        A[i+nlen]=w-A[i+nlen*]-A[i];

    }

}

int cal(int x){

    int res=;

    while(x){

        res+=x%;

        x/=;

    }

    return res;

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=,x;i<=n;i++){

        scanf("%d",&x);

        A[x]++;

    }

    int len=;

    for(int i=;i<=m;i++)

        len*=;

    fwt(A,len);

    for(int i=;i<len;i++)

        ans[cal(i)]+=A[i];

    ans[]-=n;

    for(int i=;i<=m*;i++){

        if(i)putchar(' ');

        printf("%lld",ans[i]);

    }puts("");

    return ;

}

巴特西

福建工程学院第十四届ACM校赛M题题解 fwt进阶，手推三进制fwt

第九集，结束亦是开始

题意：

思路：

代码实现

最新文章

热门文章