牛客练习赛97 G

预处理枚举答案位置，然后用卷积得到询问答案。

但是牛客机子咋怎么快呀？

$1s,10^{6}1s,10^6$ 跑 MTT 是什么鬼呀。

QAQ

#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
const dbl Pi=acos(-1);
class cpx
{
    public:
        dbl a,b;
        cpx():a(0),b(0){}
        cpx(dbl a):a(a),b(0){}
        cpx(dbl a,dbl b):a(a),b(b){}
        inline voi unit(dbl alpha){a=cos(alpha),b=sin(alpha);}
        inline cpx friend operator+(cpx a,cpx b){return cpx(a.a+b.a,a.b+b.b);}
        inline cpx friend operator-(cpx a,cpx b){return cpx(a.a-b.a,a.b-b.b);}
        inline cpx operator-(){return cpx(-a,-b);}
        inline cpx friend operator*(cpx a,cpx b){return cpx(a.a*b.a-a.b*b.b,a.b*b.a+b.b*a.a);}
        inline cpx friend operator/(cpx a,ullt v){return cpx(a.a/v,a.b/v);}
        inline cpx conj(){return cpx(a,-b);}
        inline cpx mul_i(){return cpx(-b,a);}
        inline cpx div_i(){return cpx(b,-a);}
    public:
        inline cpx&operator=(ullt v){return a=v,b=0,*this;}
        inline cpx&operator+=(cpx v){return*this=*this+v;}
        inline cpx&operator-=(cpx v){return*this=*this-v;}
        inline cpx&operator*=(cpx v){return*this=*this*v;}
        inline cpx&operator/=(ullt v){return a/=v,b/=v,*this;}
        inline dbl&real(){return a;}
        inline dbl&imag(){return b;}
};
const ullt Mod=1e9+7;
inline ullt chg(ullt v){return(v<Mod)?v:v-Mod;}
class poly
{
    private:
        std::vector<ullt>V;
    public:
        class FFT
        {
            private:
                std::vector<uint>V;std::vector<cpx>G;uint len;
            public:
                inline uint length(){return len;}
                voi bzr(uint length)
                {
                    uint p=0;len=1,V.clear(),G.clear();
                    while(length){p++,len<<=1,length>>=1;}
                    V.resize(len),G.resize(len);
                    for(uint i=0;i<len;++i)V[i]=((i&1)?(V[i>>1]|len)>>1:(V[i>>1]>>1)),G[i].unit(Pi*2/len*i);
                }
                voi fft(std::vector<cpx>&y,bol op)
                {
                    if(y.size()<len)y.resize(len);
                    for(uint i=0;i<len;i++)if(V[i]<i)std::swap(y[i],y[V[i]]);
                    for(uint h=2;h<=len;h<<=1)for(uint j=0;j<len;j+=h)for(uint k=j;k<j+(h>>1);k++){cpx u=y[k],t=G[len/h*(k-j)]*y[k+h/2];y[k]=u+t,y[k+h/2]=u-t;}
                    if(op){uint l=1,r=len-1;while(l<r)std::swap(y[l++],y[r--]);for(uint i=0;i<len;i++)y[i]/=len;}
                }
                voi fft_fft(std::vector<cpx>&a,std::vector<cpx>&b,bol op)
                {
                    if(a.size()<len)a.resize(len);
                    if(b.size()<len)b.resize(len);
                    for(uint i=0;i<len;i++)a[i]+=b[i].mul_i();
                    fft(a,op),b[0]=a[0].conj();for(uint i=1;i<len;i++)b[i]=a[len-i].conj();
                    for(uint i=0;i<len;i++){cpx p=a[i],q=b[i];a[i]=(p+q)/2llu,b[i]=(p-q).div_i()/2llu;}
                }
        };
    public:
        poly(){V.clear();}
        poly(std::vector<ullt>V){for(uint i=0;i<V.size();i++)push(V[i]%Mod);cut_zero();}
        inline bol empty(){return cut_zero(),!size();}
        inline voi bzr(){V.clear();}
        inline voi push(ullt v){V.push_back(v%Mod);}
        inline voi pop(){V.pop_back();}
        inline ullt val(uint n){return(n<V.size())?V[n]:0;}
        inline uint deg(){return V.size()-1;}
        inline uint size(){return V.size();}
        inline voi add(uint p,ullt v)
        {
            if(deg()<p)chg_deg(p);
            V[p]=(V[p]+v)%Mod;
        }
        inline poly friend operator+(poly a,ullt v){a.add(0,v);return a;}
        poly friend operator+(poly a,poly b)
        {
            uint len=std::max(a.size(),b.size());
            a.chg_siz(len),b.chg_siz(len);
            for(uint i=0;i<len;i++)a[i]=chg(a[i]+b[i]);
            a.cut_zero();
            return a;
        }
        poly friend operator-(poly a,poly b)
        {
            uint len=std::max(a.size(),b.size());
            a.chg_siz(len),b.chg_siz(len);
            for(uint i=0;i<len;i++)a[i]=chg(a[i]+Mod-b[i]);
            a.cut_zero();
            return a;
        }
        poly operator-()
        {
            cut_zero();uint len=size();
            poly ans;ans.chg_siz(len);
            for(uint i=0;i<len;i++)ans[i]=chg(Mod-V[i]);
            return ans;
        }
        poly friend operator*(poly a,poly b)
        {
            FFT s;poly p;
            uint n=a.deg(),m=b.deg(),len;
            s.bzr(n+m+1),len=s.length();
            std::vector<cpx>v1(len),v2(len),v3(len),v4(len);
            for(uint i=0;i<len;i++)v3[i]=cpx(a.val(i)&32767),v1[i]=cpx(a.val(i)>>15),v4[i]=cpx(b.val(i)&32767),v2[i]=cpx(b.val(i)>>15);
            s.fft_fft(v1,v2,0),s.fft_fft(v3,v4,0);
            for(uint i=0;i<len;i++)v4[i]=(v3[i]+v1[i].mul_i())*v4[i],v2[i]=(v3[i]+v1[i].mul_i())*v2[i];
            s.fft(v2,1),s.fft(v4,1),p.chg_deg(n+m);for(uint i=0;i<=n+m;i++)p[i]=(((ullt)(v2[i].b+.5)%Mod<<30)+((ullt)(v2[i].a+v4[i].b+.5)%Mod<<15)+(ullt)(v4[i].a+.5))%Mod;
            p.cut_zero();
            return p;
        }
        inline poly inv(){return inv(size());}
        poly inv(uint prec)
        {
            poly ans,f,tmp,w;
            llt x,y;
            exgcd<llt>(val(0),Mod,x,y);
            ans.push(x%(llt)Mod+(llt)Mod),f.push(val(0));
            for(uint k=1;k<prec;k<<=1)
            {
                for(uint i=k;i<(k<<1);++i)f.push(val(i));
                tmp=f*ans,tmp.chg_siz(k<<1),w.bzr();for(uint i=0;i<k;++i)w.push(tmp[i+k]);
                w*=ans;for(uint i=0;i<k;++i)ans.push(Mod-w[i]);
            }
            return ans;
        }
        poly diff(){uint n=size();poly ans;for(uint i=1;i<n;++i)ans.push(V[i]*i);return ans;}
        poly inte()
        {
            uint n=size();
            poly ans;
            ans.chg_deg(n);
            ullt k=1;llt x,y;
            std::vector<ullt>W;W.push_back(1),W.push_back(1);
            for(uint i=2;i<n;++i)W.push_back(k=(k*i)%Mod);
            exgcd<llt>(k*n%Mod,Mod,x,y);
            k=chg(x%(llt)Mod+(llt)Mod);
            for(uint i=n;i;--i)ans[i]=V[i-1]*k%Mod*W[i-1]%Mod,k=k*i%Mod;
            return ans;
        }
        inline poly ln(){return(this->diff()*this->inv()).inte().chg_deg_ed(deg());}
        inline poly exp(){return exp(size());}
        poly exp(uint prec)
        {
            poly m;m.push(1);
            if(empty())return m;
            uint tp=1;
            while(tp<prec)m*=*this-(m.diff()*m.inv(tp<<=1)).inte()+1,m.chg_siz(tp);
            m.chg_siz(prec);
            return m;
        }
        poly reverse(){poly ans;for(uint i=deg();~i;--i)ans.push(V[i]);return ans;}
        inline poly operator/(poly b)
        {
            cut_zero(),b.cut_zero();uint m=size(),n=b.deg();if(m<=n)return poly();
            poly f=this->reverse()*b.reverse().inv(m-n);f.chg_siz((m>n)?m-n:0);return f.reverse();
        }
        inline poly operator%(poly b){poly f=*this-*this/b*b;f.cut_zero();return f;}
        voi cut_zero(){while(!V.empty()&&!V.back())V.pop_back();}
        voi chg_siz(const uint siz){while(V.size()<siz)V.push_back(0);while(V.size()>siz)V.pop_back();}
        inline voi chg_deg(const uint d){chg_siz(d+1);}
        inline poly chg_deg_ed(const uint d){poly ans=*this;return ans.chg_deg(d),ans;}
    public:
        inline ullt&operator[](uint num){return V[num];}
        poly&operator=(std::vector<ullt>V){bzr();for(uint i=0;i<V.size();i++)push(V[i]%Mod);cut_zero();return*this;}
        poly&operator=(std::vector<cpx>V){bzr();for(uint i=0;i<V.size();i++)push((llt)(V[i].a+.5)%(llt)Mod+(llt)(Mod));cut_zero();return*this;}
        poly&operator+=(poly b){return*this=*this+b;}
        poly&operator-=(poly b){return*this=*this-b;}
        poly&operator*=(poly b){return*this=*this*b;}
        poly&operator/=(poly b){return*this=*this/b;}
        poly&operator%=(poly b){return*this=*this%b;}
};
template<const ullt p=998244353>
class mod_ullt
{
    private:
        ullt v;
        inline ullt chg(ullt w){return(w<p)?w:w-p;}
        inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
    public:
        mod_ullt():v(0){}
        mod_ullt(ullt v):v(v%p){}
        bol empty(){return!v;}
        inline ullt val(){return v;}
        friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
        friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
        friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
        friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
        friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
        friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
        inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
        inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
        inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
        friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
        inline mod_ullt operator-(){return _chg(p-v);}
        mod_ullt sqrt()
        {
            if(power(v,(p-1)>>1,p)!=1)return 0;
            mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
            ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
            mod_ullt x=_power((t+1)>>1),e=_power(t);
            while(k<s)
            {
                if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
                e=_power(p-2)*x*x,k++;
            }
            return _min(x,-x),x;
        }
        mod_ullt inv(){return _power(p-2);}
        mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
        voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
        voi print()
        {
        	static chr C[20];uint tp=0;
        	ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
        	while(tp--)putchar(C[tp]);
        }
        voi println(){print(),putchar('\n');}
        mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
    public:
        inline ullt&operator()(){return v;}
        inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
        inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
        inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
        mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
        mod_ullt&operator++(){return v=chg(v+1),*this;}
};
typedef mod_ullt<Mod>modint;
uint A[1000005],n;
modint now,QAQ[1000005],X[1000005],Y[1000005];
bol check(uint p,uint x){now++;return p<=n&&A[p]<=x;}
voi get(uint x=0)
{
    uint p=0,l=1;
    while(check(p+l,x))p+=l,l<<=1;
    while(l)
    {
        if(check(p+l,x))p+=l;
        l>>=1;
    }
}
poly P,Q;
int main()
{
    uint m,q;scanf("%u%u%u",&n,&m,&q);
    if(n>m)return puts("0"),0;
    for(uint i=1;i<=n;i++)A[i]=1;
    for(uint i=0;i<=n;i++)now=0,get(),QAQ[i]=now,A[i+1]=0;
    X[0]=1;for(uint i=1;i<=m;i++)X[i]=X[i-1]*i;
    Y[m]=X[m].inv();for(uint i=m;i;i--)Y[i-1]=Y[i]*i;
    for(uint i=0;i<=n;i++)P.push((QAQ[i]*Y[i]*Y[n-i])());
    for(uint i=0;i<=m-n;i++)Q.push((Y[i]*Y[m-n-i])());
    P=P*Q;
    for(uint i=0;i<=m;i++)QAQ[i]=P.val(i)*X[i]*X[m-i];
    ullt ans=0;
    for(uint i=1;i<=q;i++)
    {
        uint w;scanf("%u",&w);
        ans^=QAQ[w]()*i;
    }
    printf("%llu\n",ans);
    return 0;
}