题解 P5418 【[CTSC2016]NOIP十合一】

LCuter · 2020-05-29 18:18:28 · 题解

CTSC2016 NOIP十合一 题解

\text{Description}

给定一张边带权有向图与模数，多次询问一个点到另一个点间距离为某个值的路径的条数对给定模数取模的值。

注意一个细节，即任意点到其自身存在一条长度为 0 的“道路”。

提交答案题。

<!--more-->

\text{Solution}

C1

性质

形如下图：

模数为 2^{12}\times 3^8。

什么，你说懒得打质因数分解？百度质因数分解不谢。

做法

设当前询问为 u,v,w。

每一个奇数到下一个偶数的路径长为 1，每一个偶数到下一个奇数的路径长为 0。

若 u 为偶数，我们强制其退回上一个奇数，然后执行 w\gets w-1。

若 v 为偶数，我们强制其前往下一个奇数。

那么现在 u,v 都为奇数，我们考虑从某个奇数跳往下一个奇数时，有两种方案可选，一种花去 1 长度，另一种不花去长度。

设 l 表示从 u 跳到 v 要跳多少次，注意此处 w 是更新过的。

那么我们需要计算的是：

这个模数不是质数，得想个方法快速计算组合数。

然后你发现一波扩展卢卡斯定理（exLucas）解决了？

扩展卢卡斯定理

递归切题法，启动！

细节判一下就能过了，时间复杂度 1s 跑的完（

代码

#include<bits/stdc++.h>
#define REG register
using namespace std;
inline void read(int& x){
    static char c;
    while(!isdigit(c=getchar()));x=c^48;
    while(isdigit(c=getchar()))x=(x*10)+(c^48);
} 

int n,m,q,p;

inline int Pow(int a,int b,int p){
    int ans(1);
    while(b){
        if(b&1) ans=ans*a%p;
        a=a*a%p,b>>=1;
    }
    return ans;
}

inline void exgcd(int a,int b,int& x,int& y){b?(exgcd(b,a%b,y,x),y-=a/b*x):(x=1,y=0);}

int _InvX,_InvY;
int Inv(int a,int P){
    _InvY=_InvX=0;
    exgcd(a,P,_InvX,_InvY);
    return (_InvX%P+P)%P;
}

const int P1=1<<12,P2=Pow(3,8,100005);

int _2Mul[10005],_3Mul[10005];
int _2Sig[50005],_3Sig[50005];
int _2Phi[50005],_3Phi[50005];

inline void Init(){
    _2Mul[0]=_3Mul[0]=1;
    for(REG int i=1;i<P1;++i) _2Mul[i]=_2Mul[i-1]*(i%2?i:1)%P1;
    for(REG int i=1;i<P2;++i) _3Mul[i]=_3Mul[i-1]*(i%3?i:1)%P2;
    _2Phi[0]=_3Phi[0]=1;
    for(REG int i=1;i<=50000;++i)
        _2Phi[i]=_2Phi[i/2]*_2Mul[i%P1]%P1*Pow(_2Mul[P1-1],i/P1,P1)%P1,
        _3Phi[i]=_3Phi[i/3]*_3Mul[i%P2]%P2*Pow(_3Mul[P2-1],i/P2,P2)%P2;
    _2Sig[0]=_3Sig[0]=0;
    for(REG int i=1;i<=50000;++i) _2Sig[i]=_2Sig[i/2]+i/2,_3Sig[i]=_3Sig[i/3]+i/3;  
}

inline int Binom(int n,int m){
    if(n<m) return 0;
    int Pw=_2Sig[n]-_2Sig[m]-_2Sig[n-m];
    int _2Ans,_3Ans;
    if(Pw>=12) _2Ans=0;
    else _2Ans=_2Phi[n]*Inv(_2Phi[m],P1)%P1*Inv(_2Phi[n-m],P1)%P1*Pow(2,Pw,P1)%P1;
    Pw=_3Sig[n]-_3Sig[m]-_3Sig[n-m];
    if(Pw>=8) _3Ans=0;
    else _3Ans=_3Phi[n]*Inv(_3Phi[m],P2)%P2*Inv(_3Phi[n-m],P2)%P2*Pow(3,Pw,P2)%P2;
    return (1ll*_2Ans*P2%p*Inv(P2,P1)%p+1ll*_3Ans*P1%p*Inv(P1,P2)%p)%p;
}

inline void Work(){
    Init();
    read(n),read(m),read(q),read(p);
    for(REG int i=1;i<=m;++i){
        int u,v,w;
        read(u),read(v),read(w);
    }
    while(q--){
        int u,v,w;
        read(u),read(v),read(w);
        if(u==v){printf("%d\n",!w);continue;}
        if(!(v&1)) --w,--v;u|=1;
        if(w<0){puts("0");continue;}
        int Len=(v-u)>>1;
        printf("%d\n",Binom(Len,w));
    }
}

int main(){Work();}

点评

强行扩展卢卡斯，差评（

C2

性质

从点 1 到点 100 顺次相连形成一条链，且每个点上有一个自环。

询问中的 u 都为 1，w 不超过 50000。

做法

从一个数到其后继不需要花费边权。

我们可以任意挑选自环（可以重复挑选同一个自环），使得所选择自环上的边权和为 w，然后求方案数。

完全背包求方案数？

由于模数的问题，我们老老实实做 DP 就可以了，注意状态设计时不能压掉前面那一维。

都做这题了还不会完全背包？不会吧不会吧不会吧？好吧我不会……

代码

#include<bits/stdc++.h>
#define REG register
using namespace std;
inline void read(int& x){
    static char c;
    while(!isdigit(c=getchar()));x=c^48;
    while(isdigit(c=getchar()))x=(x*10)+(c^48);
} 

const int Mod=19960928;

int n,m,q,p;

int u,v,w;

int Wht[105];

int DP[105][50005];

inline void Init(){
    DP[0][0]=1;
    for(REG int i=1;i<=n;++i)
        for(REG int j=0;j<=50000;++j){
            DP[i][j]=DP[i-1][j];
            if(j>=Wht[i]) DP[i][j]=(DP[i][j]+DP[i][j-Wht[i]])%Mod;
        }
}

inline void Work(){
    read(n),read(m),read(q),read(p);
    while(m--){
        read(u),read(v),read(w);
        if(u==v) Wht[u]=w;
    }
    Init();
    for(REG int i=1;i<=q;++i){
        read(u),read(v),read(w);
        printf("%d\n",DP[v][w]);
    }
}

int main(){Work();}

点评

好像没啥好说的……

C3

性质

从点 1 到点 10^4 顺次相连形成一条链，且每个点上有一个自环。

询问中 w 不超过 1000。

模数 1998585857=953\times2^{21}+1，其原根为 3。

做法

跟 C2 差不多，但是数据范围上有从量到质的变化。

如果直接 DP，那么 C3 会跑死，这时候就要祭出多项式了。

设第 i 个物品的生成函数为 F_i(x)，其重量为 w_i，那么它的生成函数是很容易写出来的（除了 w_i 的倍数上有 1 其它都为 0，注意这边认为 0 也是 w_i 的倍数）。

每次询问我们只需求出某一个区间内所有物品的生成函数的乘积。

注意到询问中 w 不超过 1000，故多项式最多只有 1001 项。

预处理前缀生成函数乘积与其逆即可。

注意 1998585857 加起来会爆 int。

代码

#include<bits/stdc++.h>
#define int long long
#define REG register
using namespace std;
inline void read(int& x){
    static char c;
    while(!isdigit(c=getchar()));x=c^48;
    while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

const int Mod=1998585857,lim=2048,L=11,G=3,InvG=666195286;

namespace Polynomial{
    #define MAXN 50005

    inline void Swap(int& a,int& b){int t=a;a=b,b=t;}
    inline int Add(int a,int b){return (a+=b)>=Mod?a-Mod:a;}
    inline int Del(int a,int b){return (a-=b)<0?a+Mod:a;}
    inline int Min(int a,int b){return a<b?a:b;}

    inline int Pow(int a,int b){
        int ans(1);
        while(b){
            if(b&1) ans=1ll*ans*a%Mod;
            a=1ll*a*a%Mod,b>>=1;
        }
        return ans;
    }

    int NumInv[MAXN];
    int PosSt[55],NegSt[55];

    inline void Predone(){
        NumInv[1]=1;
        for(REG int i=2;i<=MAXN-5;++i) NumInv[i]=1ll*(Mod-Mod/i)*NumInv[Mod%i]%Mod;
        for(REG int i=1;i<=30;++i) PosSt[i]=Pow(3,(Mod-1)/(1<<i)),NegSt[i]=Pow(PosSt[i],Mod-2);
    }

    int Rev[MAXN];

    inline void GetRev(int len,int L){
        for(REG int i=1;i<len;++i)
            Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(L-1));
    }

    inline void NTT(int* A,int len,short op){
        for(REG int i=1;i<len;++i)
            if(i<Rev[i]) Swap(A[i],A[Rev[i]]);
        for(REG int i=1,j=1;i<len;i<<=1,++j){
            int Stp=op?PosSt[j]:NegSt[j];
            for(REG int j=0;j<len;j+=(i<<1)){
                int Tmp=1;
                for(REG int k=0;k<i;++k,Tmp=1ll*Tmp*Stp%Mod){
                    int x=*(A+j+k),y=1ll*Tmp*(*(A+j+k+i))%Mod;
                    *(A+j+k)=Add(x,y);
                    *(A+j+k+i)=Del(x,y);
                }
            }
        }
        if(!op){
            int Invlen=NumInv[len];
            for(REG int i=0;i<len;++i) A[i]=1ll*A[i]*Invlen%Mod;
        }
    }

    int MulA[MAXN],MulB[MAXN];

    inline void Mul(int* A,int* B,int* C,int len){
        memset(MulA,0,sizeof(MulA)),memset(MulB,0,sizeof(MulB));
        for(REG int i=0;i<(len>>1);++i)
            MulA[i]=A[i],MulB[i]=B[i];
        NTT(MulA,len,1),NTT(MulB,len,1);
        for(REG int i=0;i<len;++i)
            MulA[i]=1ll*MulA[i]*MulB[i]%Mod;
        NTT(MulA,len,0);
        for(REG int i=0;i<len;++i) C[i]=MulA[i];
    }

    int InvB[2][MAXN],InvCur;
    int InvTmpG[MAXN];

    inline void Inv(int* A,int* B,int len){
        InvCur=0,memset(InvB,0,sizeof(InvB)),memset(InvTmpG,0,sizeof(InvTmpG));
        int Now=1,Nxt=2,NxtL=1;
        InvB[0][0]=Pow(A[0],Mod-2);
        GetRev(Nxt,NxtL);
        while(Now<=(len<<1)){
            InvCur^=1,memset(InvB[InvCur],0,sizeof(InvB[InvCur]));
            for(REG int i=0;i<Now;++i) InvB[InvCur][i]=Add(InvB[InvCur^1][i]<<1,0);
            for(REG int i=0;i<Now;++i) InvTmpG[i]=InvB[InvCur^1][i];
            for(REG int i=0;i<Now;++i) InvB[InvCur^1][i]=A[i];
            NTT(InvTmpG,Nxt,1),NTT(InvB[InvCur^1],Nxt,1);
            for(REG int i=0;i<Nxt;++i) InvB[InvCur^1][i]=1ll*InvB[InvCur^1][i]*InvTmpG[i]%Mod;
            for(REG int i=0;i<Nxt;++i) InvB[InvCur^1][i]=1ll*InvB[InvCur^1][i]*InvTmpG[i]%Mod;
            NTT(InvB[InvCur^1],Nxt,0);
            for(REG int i=0;i<Now;++i) InvB[InvCur][i]=Del(InvB[InvCur][i],InvB[InvCur^1][i]);
            Now<<=1,Nxt<<=1,++NxtL;
            if(Now<=(len<<1)) GetRev(Nxt,NxtL);
        }
        for(REG int i=0;i<=len;++i) B[i]=InvB[InvCur][i];
    }

    inline void Int(int* A,int* B,int len){for(REG int i=1;i<=len;++i) B[i]=1ll*A[i-1]*Pow(i,Mod-2)%Mod;B[0]=0;}
    inline void Der(int* A,int* B,int len){for(REG int i=1;i<=len;++i) B[i-1]=1ll*i*A[i]%Mod;B[len]=0;}

    int LnDer[MAXN],LnInv[MAXN];

    inline void Ln(int* A,int* B,int len){
        Der(A,LnDer,len),Inv(A,LnInv,len);
        int lim=1,L=0;
        while(lim<=(len<<1)) lim<<=1,++L;
        GetRev(lim,L);
        Mul(LnDer,LnInv,LnDer,lim);
        Int(LnDer,B,len);
    }

    int ExpB[2][MAXN],ExpCur,ExpLn[MAXN];

    inline void Exp(int* A,int* B,int len){
        ExpCur=0,memset(ExpB,0,sizeof(ExpB));
        int Now=1,Nxt=2,NxtL=1;
        ExpB[0][0]=1;
        GetRev(Nxt,NxtL);
        while(Now<=(len<<1)){
            ExpCur^=1,memset(ExpB[ExpCur],0,sizeof(ExpB[ExpCur]));
            Ln(ExpB[ExpCur^1],ExpLn,Now-1);
            for(REG int i=0;i<Now;++i) ExpLn[i]=Del(A[i]+(i==0),ExpLn[i]);
            Mul(ExpB[ExpCur^1],ExpLn,ExpB[ExpCur],Nxt);
            Now<<=1,Nxt<<=1,++NxtL;
            if(Now<=(len<<1)) GetRev(Nxt,NxtL);
        }
        for(REG int i=0;i<=len;++i) B[i]=ExpB[ExpCur][i];
    }

    inline void PolyPow(int* A,int* B,int k,int len){
        Ln(A,B,len);
        for(REG int i=0;i<=len;++i) B[i]=1ll*B[i]*k%Mod;
        Exp(B,B,len);
    }
}

using namespace Polynomial;

int n,m,q,p;

int u,v,w;

int Poly[10005][2505],Ioly[10005][2505];

int Tmpa[3005],Tmpb[3005]; 

inline void Work(){
    Predone();
    freopen("noip3.in","r",stdin);
    freopen("noip3.out","w",stdout);
    read(n),read(m),read(q),read(p);
    Poly[0][0]=Ioly[0][0]=1;
    for(REG int i=1;i<=m;++i){
        read(u),read(v),read(w);
        if(u==v){
            GetRev(lim,L);
            for(REG int j=0;j<=1000;j+=w) Poly[u][j]=1;
            for(REG int j=0;j<lim;++j) Tmpa[j]=Poly[u-1][j];
            NTT(Tmpa,lim,1),NTT(Poly[u],lim,1);
            for(REG int j=0;j<2048;++j) Poly[u][j]=1ll*Tmpa[j]*Poly[u][j]%Mod;
            NTT(Poly[u],lim,0);
            for(REG int j=1001;j<=2048;++j) Poly[u][j]=0;
            Inv(Poly[u],Ioly[u],1000);
        }
    }
    GetRev(lim,L);
    for(REG int i=1;i<=q;++i){
        read(u),read(v),read(w);
        memset(Tmpa,0,sizeof Tmpa);
        memset(Tmpb,0,sizeof Tmpb);
        for(REG int j=0;j<=1000;++j) Tmpa[j]=Poly[v][j],Tmpb[j]=Ioly[u-1][j];
        NTT(Tmpa,lim,1),NTT(Tmpb,lim,1);
        for(REG int j=0;j<lim;++j) Tmpa[j]=1ll*Tmpa[j]*Tmpb[j]%Mod;
        NTT(Tmpa,lim,0);
        printf("%d\n",Tmpa[w]);
        if(i==1) cerr<<Tmpa[w]<<endl;
    }
}

signed main(){Work();}

点评

啥也不说了，998244353 天下第一！！

C4

性质