ZJT's Blog

大変に気分がいい~

动态图连通性问题的在线解法

2018-4-17 2:252018-4-17 2:25
动态图Euler-tour Tree毒瘤

最近居然在省选模拟赛里面做到了这个毒瘤问题。。

动态图连通性问题是指维护一个不断加边删边的无向图,要求查询两个点之间的连通性,以及支持对连通块的各种信息的维护。离线的话非常好做,直接处理出每条边的删除时间后,维护关于删除时间的最大生成树即可。强制在线的话,也有一个$O(\log^2n)$的做法,是通过将图分层并用ETT维护每一层的生成树来解决的。不过这个算法实现起来比较复杂,第一次写完+调试完大概花了6h,估计场上想写是不太可能的了。。

为了维护连通性的信息,我们可以考虑维护生成森林。我们给每条边钦点一个非负整数的等级(level),定义$G_i$为所有等级为$i$的边构成的子图,$T_i$为所有等级大于等于$i$的边构成的图中,关于等级的最大生成森林。最终询问的时候,直接在$T_0$上做询问就行了。

当一条新边加入时,我们先令它的等级为$0$。这时,我们会在$G_0$中加入这条边,如果$T_0$中加入这条边不会形成环,我们也把它加入$T_0$。

删除的情况比较复杂。如果删掉的是一条不在$T_0$中的边,那它也不可能在任何$T_i$中出现,我们直接在对应等级的$G_i$中把它删掉就行了。然而如果我们要删掉一条树边,则可能存在一条非树边,使得删掉这条树边形成两个连通块可以被这条非树边连接。这时候这条非树边就会取代删去的边,成为新的树边。

考虑如何在图中找到这条非树边。我们记删去的边为$e_0$,等级为$l_0$,替换它的非树边为$e_1$,等级为$l_1$。显然$l_1\leq l_0$,否则最大生成森林的性质就不满足了($e_1$可以替代$e_0$得到一个更大的生成森林)。

我们考虑从$l_0$到$0$枚举$l_1$,看看是否存在等级为$l_1$的非树边$e_1$能替换删去的$e_0$。一个比较显然的结论是$e_1$连接的两个端点一定在$T_{l_1}$上与$e_0$的端点连通,这个可以通过MST的性质得到。记$e_0$在$T_{l_1}$上连接的两个连通块为$X,Y$,且$|X|\leq|Y|$,考虑一个暴力做法,我们直接在$G_{l_1}$中枚举每条从$X$连出去的边,如果连出去的边位于$Y$中,则找到了$e_1$。如果枚举完每条边之后还是没找到,则说明不存在等级为$l_1$的满足条件的$e_1$。

这样做的复杂度显然是错的,我们考虑对它进行优化。我们在暴力枚举每条边的时候 ,如果这条边不能满足条件,就把它的等级$+1$(在$G_{l_1}$中删去它,在$G_{l_1+1}$中加入它,如果它是树边还要在$T_{l_1+1}$中也加入它)。这样每次访问到一条边时,要么找到了答案,要么这条边的等级增加,所以我们暴力枚举的复杂度就只跟每条边的最大等级有关了(等级增加次数肯定不会超过最大等级)。同时,我们还可以证明,$T_i$中的最大连通块大小是$O(n/2^i)$级别的。因为我们每次都是只处理从较小的连通块中连出的边($|X|\leq|Y|$),且在我们把所有边升级完之后,下一等级的生成树上形成的连通块大小也不会超过$|X|$(因为当前层的生成树一定包含下一层的生成树),所以每一层的连通块大小的上界都会减半。这也说明了边的最大等级是$O(\log n)$级别的,即每条边都最多只会被升级$O(\log n)$次。

我们用ETT维护$T_i$中有哪些点有$G_i$的连边,这样每次搜索的复杂度就是$O($搜到的边数$\times\log n)$的,在ETT中的link和cut也是$O(\log n)$的,所以总复杂度为$O(m\log^2 n)$。这样就成功解决了这个问题。

实现上可能有一些细节问题要注意,首先在搜索$X$的出边时,要先搜所有的树边。如果先搜了非树边,可能会因为非树边等级的提高而出现生成树心态发生改变的情况,这种情况是不好处理的。其次对边的搜索要一边搜索一边检查是否可行,如果先搜出了所有边再一个个判断,复杂度就是错的,在loj上会被卡(

这是模板题

附上代码实现一份(loj垫底qwq):

#include <bits/stdc++.h>
#define MAXN 500010
#define MAXL 20
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n,m,online;
int v[MAXN];

namespace Duliu{
    int ls[MAXN],numls;

    struct ETT{
        struct node{
            int lc,rc,p,key,size,pt;
            bool tag,stag;
        }a[MAXN<<1];

        int blist[MAXN],numb;
        int p[MAXN];
        map<int,int> e[MAXN];
        int tagp[MAXN];

        ETT(int n){
            for(int i=2*n;i>=1;i--) a[blist[++numb]=i].key=rand();
        }

        int newnode(int pt){
            int x=blist[numb--];
            a[x].p=a[x].lc=a[x].rc=a[x].tag=a[x].stag=0;
            a[x].size=1;
            a[x].pt=pt;
            return x;
        }

        void delnode(int x){
            blist[++numb]=x;
        }

        inline void pushup(int x){
            a[x].stag=a[a[x].lc].stag||a[a[x].rc].stag||a[x].tag;
            a[x].size=a[a[x].lc].size+a[a[x].rc].size+1;
        }

        int merge(int x,int y){
            if(!x || !y) return x+y;
            if(a[x].key<a[y].key){
                a[x].rc=merge(a[x].rc,y);
                a[a[x].rc].p=x;
                pushup(x);
                return x;
            }else{
                a[y].lc=merge(x,a[y].lc);
                a[a[y].lc].p=y;
                pushup(y);
                return y;
            }
        }

        pair<int,int> split(int x,int d){
            int s1=a[x].lc,s2=a[x].rc;
            if(d==-1){
                a[x].rc=0;
                pushup(x);
                s1=x;
                a[s2].p=0;
            }else if(d==1){
                a[x].lc=0;
                pushup(x);
                s2=x;
                a[s1].p=0;
            }else a[s1].p=a[s2].p=0;
            while(a[x].p){
                int p=a[x].p;
                if(a[p].lc==x){
                    a[p].lc=s2;
                    a[s2].p=p;
                    a[s1].p=0;
                    s2=p;
                }else{
                    a[p].rc=s1;
                    a[s1].p=p;
                    a[s2].p=0;
                    s1=p;
                }
                pushup(x=p);
            }
            return make_pair(s1,s2);
        }

        int getRoot(int x){
            while(a[x].p) x=a[x].p;
            return x;
        }

        int get_p(int x){
            if(e[x].empty()) return 0;
            return e[e[x].begin()->first][x];
        }

        void link(int x,int y){
            int p1=newnode(y),p2=newnode(x);
            if(tagp[x]==-1){
                tagp[x]=p2;
                a[p2].tag=a[p2].stag=1;
            }
            if(tagp[y]==-1){
                tagp[y]=p1;
                a[p1].tag=a[p1].stag=1;
            }
            int t1,t2,t3;
            if(e[x].empty()) t1=t3=0;
            else{
                pair<int,int> temp=split(e[x].begin()->second,1);
                t1=temp.first; t3=temp.second;
            }
            if(e[y].empty()) t2=0;
            else{
                pair<int,int> temp=split(e[y].begin()->second,1);
                t2=merge(temp.second,temp.first);
            }
            e[x][y]=p1; e[y][x]=p2;
            merge(merge(merge(t1,p1),t2),merge(p2,t3));
        }

        void cut(int x,int y){
            int p1=e[x][y],p2=e[y][x];
            e[x].erase(e[x].find(y));
            e[y].erase(e[y].find(x));
            pair<int,int> t1=split(p1,0);
            if(getRoot(p2)==t1.first){
                pair<int,int> t2=split(p2,0);
                merge(t2.first,t1.second);
            }else{
                pair<int,int> t2=split(p2,0);
                merge(t1.first,t2.second);
            }
            if(a[p1].tag){
                if(e[y].empty()) tagp[y]=-1;
                else{
                    tagp[y]=get_p(y);
                    a[tagp[y]].tag=1;
                    for(int i=tagp[y];i;i=a[i].p) pushup(i);
                }
            }
            if(a[p2].tag){
                if(e[x].empty()) tagp[x]=-1;
                else{
                    tagp[x]=get_p(x);
                    a[tagp[x]].tag=1;
                    for(int i=tagp[x];i;i=a[i].p) pushup(i);
                }
            }
            delnode(p1); delnode(p2);
        }

        void setTag(int x,int v){
            if(v==1){
                int p=get_p(x);
                if(!p){
                    tagp[x]=-1;
                    return;
                }
                x=tagp[x]=p;
            }else{
                int t=tagp[x];
                tagp[x]=0;
                x=t;
                if(x==-1){
                    tagp[x]=0;
                    return;
                }
            }
            a[x].tag=v;
            while(x){
                pushup(x);
                x=a[x].p;
            }
        }

        int get_size(int x){
            if(!x) return 1;
            return a[getRoot(x)].size/2+1;
        }

        void dfs1(int x,int i);
        bool dfs2(int x,int i,int py);
    }*s[MAXL];

    int l;
    map<int,int> gl[MAXN];
    set<int> g[MAXL][MAXN];
    pair<int,int> res_e;

    void init(int n){
        for(l=0;(1<<l)<n;l++);
        for(int i=0;i<=l;i++) s[i]=new ETT(n);
    }

    bool link(int x,int y){
        gl[x][y]=0;
        gl[y][x]=0;
        bool flagx=g[0][x].empty(),flagy=g[0][y].empty();
        g[0][x].insert(y);
        g[0][y].insert(x);
        int px=s[0]->get_p(x),py=s[0]->get_p(y);
        if(!px || !py || s[0]->getRoot(px)!=s[0]->getRoot(py)){
            s[0]->link(x,y);
            if(flagx) s[0]->setTag(x,1);
            if(flagy) s[0]->setTag(y,1);
            return 1;
        }
        if(flagx) s[0]->setTag(x,1);
        if(flagy) s[0]->setTag(y,1);
        return 0;
    }

    void level_up(int x,int y,int curl){
        if(g[curl][x].empty()) s[curl]->setTag(x,0);
        if(g[curl][y].empty()) s[curl]->setTag(y,0);
        gl[x][y]++;
        gl[y][x]++;
        bool flagx=g[curl+1][x].empty(),flagy=g[curl+1][y].empty();
        g[curl+1][x].insert(y);
        g[curl+1][y].insert(x);
        int px=s[curl+1]->get_p(x),py=s[curl+1]->get_p(y);
        if(!px || !py || s[curl+1]->getRoot(px)!=s[curl+1]->getRoot(py)) s[curl+1]->link(x,y);
        if(flagx) s[curl+1]->setTag(x,1);
        if(flagy) s[curl+1]->setTag(y,1);
    }

    void gao_1(int x,int i){
        auto it=g[i][x].begin();
        while(it!=g[i][x].end()){
            if(s[i]->e[x].count(*it)){
                int y=*it;
                g[i][y].erase(g[i][y].find(x));
                it=g[i][x].erase(it);
                level_up(x,y,i);
            }else it++;
        }
    }

    bool gao_2(int x,int i,int py){
        auto it=g[i][x].begin();
        while(it!=g[i][x].end()){
            if(s[i]->getRoot(s[i]->get_p(*it))==py){
                for(int k=0;k<=i;k++)
                    s[k]->link(x,*it);
                res_e=make_pair(x,*it);
                return 1;
            }else{
                int y=*it;
                g[i][y].erase(g[i][y].find(x));
                it=g[i][x].erase(it);
                level_up(x,y,i);
            }
        }
        return 0;
    }

    pair<int,int> cut(int x,int y){
        int curl=gl[x][y];
        gl[x].erase(gl[x].find(y));
        gl[y].erase(gl[y].find(x));
        g[curl][x].erase(g[curl][x].find(y));
        g[curl][y].erase(g[curl][y].find(x));
        if(s[0]->e[x].count(y)){
            for(int i=0;i<=curl;i++) s[i]->cut(x,y);
            for(int i=curl;i>=0;i--){
                int px=s[i]->get_p(x),py=s[i]->get_p(y);
                int sx=s[i]->get_size(px),sy=s[i]->get_size(py);
                if(sy<sx) swap(x,y),swap(sx,sy),swap(px,py);
                py=s[i]->getRoot(py);
                px=s[i]->getRoot(px);
                if(px){
                    s[i]->dfs1(px,i);
                    if(s[i]->dfs2(px,i,py)) return res_e;
                }else{
                    gao_1(x,i);
                    if(gao_2(x,i,py)) return res_e;
                }
            }
            return make_pair(0,0);
        }
        return make_pair(-1,0);
    }

    bool check(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                bool flag=0;
                for(int k=l;k>=0;k--)
                    if(s[k]->e[i].count(j)) flag=1;
                    else if(flag) return 0;
            }
        return 1;
    }

    void ETT::dfs1(int x,int i){
        if(!a[x].stag) return;
        if(a[x].tag) gao_1(a[x].pt,i);
        if(a[a[x].lc].stag) dfs1(a[x].lc,i);
        if(a[a[x].rc].stag) dfs1(a[x].rc,i);
    }

    bool ETT::dfs2(int x,int i,int py){
        if(!a[x].stag) return 0;
        if(a[x].tag) if(gao_2(a[x].pt,i,py)) return 1;
        return dfs2(a[x].lc,i,py) || dfs2(a[x].rc,i,py);
    }
}

void link(int x,int y){ Duliu::link(x,y); }
void cut(int x,int y){ Duliu::cut(x,y); }

bool query(int x,int y){
    using namespace Duliu;
    if(x==y) return 1;
    int px=s[0]->get_p(x),py=s[0]->get_p(y);
    return px && py && s[0]->getRoot(px)==s[0]->getRoot(py);
}

int main(){
#ifdef DEBUG
    freopen("122.in","r",stdin);
#endif
    n=read(); m=read(); online=1;
    Duliu::init(n);
    int lastans=0;
    while(m--){
        int t=read(),x=read(),y=read();
        if(online){
            x^=lastans;
            y^=lastans;
        }
        if(t==0) link(x,y);
        if(t==1) cut(x,y);
        if(t==2){
            if(query(x,y)){
                lastans=x;
                puts("Y");
            }else{
                lastans=y;
                puts("N");
            }
        }
    }
    return 0;
}

查看详细内容

[自选题 #114] 皇城PK

2017-12-22 18:302018-4-17 2:26
集训队作业自选题生成函数FFT毒瘤

传送门

记小R所有技能的最大伤害值为$T$。我们可以钦定小R在恶龙对他造成的伤害达到$T$时放一个技能抵消掉一些伤害,然后在恶龙放完全部技能后再放一些技能来把剩下的伤害抵消掉。显然按这种方法统计的话,答案不会漏算或算重。

我们记生成函数$B(x)=x^T-\sum_ix^{T-r_i}$。这样,记$A(x)=(\sum_ix^{d_i})^K\bmod B(x)$,则$A(x)$的$k$次项系数表示的就是恶龙放完$K$轮技能后剩下$k$点伤害的方案数。这是因为恶龙每造成$1$点伤害,我们可以看成是对生成函数乘$x$,而达到$T$后放一个技能则可以看成对$B(x)$取模。所以在模$B(x)$意义下做快速幂就行啦。

然后写完之后发现卡常数。。。最后卡得怀疑人生才过掉,代码从5K加到9K。。。。(其实有很多无意义的重复,应该能缩得更短,四毛子优化也没加,加了估计就不用卡常了。。。)

#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <algorithm>
#define MAXN 33000
#define MAXW 32768
#define LL long long
using namespace std;

const LL P=1000000007;
const double PI=acos(-1.0);

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

struct cplx{
    double r,i;
    cplx(double _r=0,double _i=0):r(_r),i(_i){}
    friend cplx operator+(cplx x,cplx y){ return cplx(x.r+y.r,x.i+y.i); }
    friend cplx operator-(cplx x,cplx y){ return cplx(x.r-y.r,x.i-y.i); }
    friend cplx operator*(cplx x,cplx y){ return cplx(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r); }
}w[MAXN],tb1[MAXN],tb2[MAXN],tb3[MAXN],tbi1[MAXN],tbi2[MAXN],tbi3[MAXN];

int n,m1,m2;
LL K;
LL v1[MAXN],v2[MAXN];
LL b[MAXN],b2[MAXN],b2inv[MAXN];
LL g[MAXN];

void FFT(cplx *a,int len,int flag){
    static int rev[MAXN],revlen;
    if(revlen!=len){
        revlen=len;
        for(int i=1;i<len;i++)
            rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    }
    for(int i=0;i<len;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int l=2;l<=len;l<<=1){
        int l2=l>>1;
        for(int i=0;i<=len;i+=l){
            for(int j=0;j<l2;j++){
                cplx t1=a[i+j],t2=a[i+j+l2]*w[MAXW/l*j];
                a[i+j]=t1+t2;
                a[i+j+l2]=t1-t2;
            }
        }
    }
    if(flag==-1){
        for(int i=1;i<len;i++)
            if(i<len-i)
                swap(a[i],a[len-i]);
        for(int i=0;i<len;i++){
            a[i].r/=len;
            a[i].i/=len;
        }
    }
}

void pre_gao_inv_b(LL *b,int n){
    static cplx t1[MAXN],t2[MAXN];
    int sizew=1;
    for(sizew=1;sizew<=2*n;sizew<<=1);
    for(int i=0;i<=n;i++) if(b[i]<0) b[i]+=P;
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++) t2[i].r=b[i]/10000;
    FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) tbi1[i]=t2[i];
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++) t2[i].r=b[i]/10000+b[i]%10000;
    FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) tbi2[i]=t2[i];
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++) t2[i].r=b[i]%10000;
    FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) tbi3[i]=t2[i];
}

void pre_gao_b(LL *b,int n){
    static cplx t1[MAXN],t2[MAXN];
    int sizew=1;
    for(sizew=1;sizew<=n;sizew<<=1);
    for(int i=0;i<=n;i++) if(b[i]<0) b[i]+=P;
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++) t2[i].r=b[i]/10000;
    FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) tb1[i]=t2[i];
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++) t2[i].r=b[i]/10000+b[i]%10000;
    FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) tb2[i]=t2[i];
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++) t2[i].r=b[i]%10000;
    FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) tb3[i]=t2[i];
}

void mul(LL *a,LL *b,LL *c,int n,bool double_n=1){
    static cplx t1[MAXN],t2[MAXN];
    static LL temp[MAXN];
    int sizew=1;
    if(double_n) for(sizew=1;sizew<=2*n;sizew<<=1);
    else for(sizew=1;sizew<=n;sizew<<=1);
    for(int i=0;i<=n;i++){
        if(a[i]<0) a[i]+=P;
        if(b[i]<0) b[i]+=P;
    }
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx(),temp[i]=0;
    for(int i=0;i<=n;i++){
        t1[i].r=a[i]/10000;
        t2[i].r=b[i]/10000;
    }
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(10000*10000-10000))%P;
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++){
        t1[i].r=a[i]/10000+a[i]%10000;
        t2[i].r=b[i]/10000+b[i]%10000;
    }
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*10000)%P;
    for(int i=0;i<sizew;i++) t1[i]=t2[i]=cplx();
    for(int i=0;i<=n;i++){
        t1[i].r=a[i]%10000;
        t2[i].r=b[i]%10000;
    }
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(1-10000))%P;
    for(int i=0;i<sizew;i++) c[i]=temp[i];
}

void mul2(LL *a,LL *b,LL *c,int n,bool double_n=1){
    static cplx t1[MAXN];
    static LL temp[MAXN];
    int sizew=1;
    if(double_n) for(sizew=1;sizew<=2*n;sizew<<=1);
    else for(sizew=1;sizew<=n;sizew<<=1);
    for(int i=0;i<=n;i++){
        if(a[i]<0) a[i]+=P;
        if(b[i]<0) b[i]+=P;
    }
    for(int i=0;i<sizew;i++) t1[i]=cplx(),temp[i]=0;
    for(int i=0;i<=n;i++) t1[i].r=a[i]/10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t1[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(10000*10000-10000))%P;
    for(int i=0;i<sizew;i++) t1[i]=cplx();
    for(int i=0;i<=n;i++) t1[i].r=a[i]/10000+a[i]%10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t1[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*10000)%P;
    for(int i=0;i<sizew;i++) t1[i]=cplx();
    for(int i=0;i<=n;i++) t1[i].r=a[i]%10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t1[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(1-10000))%P;
    for(int i=0;i<sizew;i++) c[i]=temp[i];
}

void mul3(LL *a,LL *c,int n,bool double_n=1){
    static cplx t1[MAXN],t2[MAXN];
    static LL temp[MAXN];
    int sizew=1;
    if(double_n) for(sizew=1;sizew<=2*n;sizew<<=1);
    else for(sizew=1;sizew<=n;sizew<<=1);
    for(int i=0;i<=n;i++) if(a[i]<0) a[i]+=P;
    for(int i=0;i<sizew;i++) t1[i]=cplx(),temp[i]=0;
    for(int i=0;i<=n;i++) t1[i].r=a[i]/10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*tb1[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(10000*10000-10000))%P;
    for(int i=0;i<sizew;i++) t1[i]=cplx();
    for(int i=0;i<=n;i++) t1[i].r=a[i]/10000+a[i]%10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*tb2[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*10000)%P;
    for(int i=0;i<sizew;i++) t1[i]=cplx();
    for(int i=0;i<=n;i++) t1[i].r=a[i]%10000;
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*tb3[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(1-10000))%P;
    for(int i=0;i<sizew;i++) c[i]=temp[i];
}

void mul4(LL *a,LL *c,int n,bool double_n=1){
    static cplx t1[MAXN],t2[MAXN];
    static LL temp[MAXN];
    int sizew=1;
    if(double_n) for(sizew=1;sizew<=2*n;sizew<<=1);
    else for(sizew=1;sizew<=n;sizew<<=1);
    for(int i=0;i<=n;i++) if(a[i]<0) a[i]+=P;
    for(int i=0;i<sizew;i++) t1[i]=cplx(),temp[i]=0;
    for(int i=0;i<=n;i++) t1[i].r=a[i]/10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*tbi1[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(10000*10000-10000))%P;
    for(int i=0;i<sizew;i++) t1[i]=cplx();
    for(int i=0;i<=n;i++) t1[i].r=a[i]/10000+a[i]%10000;
    FFT(t1,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*tbi2[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*10000)%P;
    for(int i=0;i<sizew;i++) t1[i]=cplx();
    for(int i=0;i<=n;i++) t1[i].r=a[i]%10000;
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*tbi3[i];
    FFT(t1,sizew,-1);
    for(int i=0;i<sizew;i++)
        temp[i]=(temp[i]+(LL)(t1[i].r+0.3)%P*(1-10000))%P;
    for(int i=0;i<sizew;i++) c[i]=temp[i];
}

void getInv(LL *a,LL *b,int n){
    b[0]=getPow(a[0],P-2);
    for(int i=1;i<=n;i++){
        b[i]=0;
        for(int j=1;j<=i;j++)
            b[i]=(b[i]-a[j]*b[i-j])%P;
        b[i]=b[i]*b[0]%P;
    }
}

void getMod(LL *a,int n,int m){
    static LL a2[MAXN],t1[MAXN],t2[MAXN];
    for(int i=0;i<=n;i++) a2[i]=a[n-i];
    for(int i=0;i<=n;i++) a[i]=0;
    mul4(a2,t1,n-m);
    for(int i=n-m+1;i<=2*(n-m);i++) t1[i]=0;
    mul3(t1,t2,m,0);
    int sizew=1;
    for(sizew=1;sizew<=m;sizew<<=1);
    for(int i=0;i<sizew;i++) t2[i]=-t2[i];
    for(int i=0;i<=n;i++) t2[i%sizew]=(a2[i]+t2[i%sizew])%P;
    for(int i=0;i<=m-1;i++)
        a[m-1-i]=t2[(i+n-m+1)%sizew];
}

int debug_time;

void getPolyPow(LL *a,LL y){
    static LL t1[MAXN];
    memset(t1,0,sizeof t1);
    t1[0]=1;
    while(y){
        if(y&1){
            mul(t1,a,t1,n-1);
            getMod(t1,2*(n-1),n);
        }
        mul2(a,a,a,n-1);
        getMod(a,2*(n-1),n);
        y>>=1;
    }
    for(int i=0;i<n;i++)
        a[i]=t1[i];
}

void init(){
    for(int i=0;i<MAXW;i++)
        w[i]=cplx(cos(2*PI/MAXW*i),sin(2*PI/MAXW*i));
    b[n]=1;
    for(int i=1;i<=m2;i++) b[n-v2[i]]--;
    for(int i=0;i<=n;i++) b2[i]=b[n-i];
    getInv(b2,b2inv,n);
    g[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m2;j++)
            if(v2[j]<=i)
                g[i]=(g[i]+g[i-v2[j]])%P;
    pre_gao_b(b2,n);
    pre_gao_inv_b(b2inv,n-2);
}

LL solve(){
    static LL t1[MAXN],t2[MAXN];
    for(int i=1;i<=m1;i++){
        memset(t1,0,sizeof t1);
        t1[1]=1;
        getPolyPow(t1,v1[i]);
        for(int j=0;j<n;j++)
            t2[j]=(t2[j]+t1[j])%P;
    }
    getPolyPow(t2,K);
    LL ans=0;
    for(int i=0;i<n;i++)
        ans=(ans+g[i]*t2[i])%P;
    ans=(ans+P)%P;
    return ans;
}

int main(){
#ifdef DEBUG
    freopen("114.in","r",stdin);
#endif
    scanf("%d%d%lld",&m1,&m2,&K);
    for(int i=1;i<=m1;i++) scanf("%lld",v1+i);
    for(int i=1;i<=m2;i++){
        scanf("%lld",v2+i);
        if(v2[i]>n) n=v2[i];
    }
    init();
    printf("%lld\n",solve());
#ifdef DEBUG
    printf("debug:%d\n",debug_time);
#endif
    return 0;
}

查看详细内容