「考试总结」2021.11.2 多校联测

· · 个人记录

A.按位或

定义 x 的子集为所有与 x 按位或起来为 x 的数

考虑子集反演，算出能拼出 x 的所有子集的方案数的和 g(x)，有：

f(x)=\sum\limits_{T\subseteq x}(-1)^{|x|-|T|}g(T)

然后观察发现 2^i\bmod 3 的剩余系只有 1,2，且只要这两种位个数相等，它按位或出 3 的倍数的方案总是相等的

那么枚举 x 的位中 \bmod 3 为 1,2 的各有多少种，求方案数直接背包即可

时间复杂度 O(\log t^2(\log t+\log n))

#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned long long
#define fir first
#define sec second
using namespace std;
namespace IO{
    #define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout);
    #define fill(a,b,c,d) memset(a,b,sizeof(c)*(d+1))
    #define copy(a,b,c,d) memcpy(a,b,sizeof(c)*(d+1))
    #define fillall(x,y) memset(x,y,sizeof(x))
    #define copyall(x,y) memcpy(x,y,sizeof(x))
    inline ll read(){
        ll w=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
        while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
        return w*f;
    }
}
using namespace IO;
namespace CL{

    const int mod=998244353;

    ll n,t,ans; int cnt1,cnt2;
    ll fac[61],inv[61],f[2][3];
    inline ll qpow(ll x,ll y){
        ll res=1;
        for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
        return res;
    }
    inline ll C(int n,int m){
        if(m>n) return 0;
        return fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    inline void init(){
        fac[0]=inv[0]=1;
        for(int i=1;i<=60;i++) fac[i]=fac[i-1]*i%mod;
        inv[60]=qpow(fac[60],mod-2);
        for(int i=59;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    }
    inline ll calc(int c1,int c2){
        fillall(f,0); f[0][0]=1;
        for(int i=1,cur=i&1;i<=c1;i++,cur^=1){
            f[cur][0]=f[cur^1][2]+f[cur^1][0];
            f[cur][1]=f[cur^1][0]+f[cur^1][1];
            f[cur][2]=f[cur^1][1]+f[cur^1][2];
        }
        for(int i=1,cur=(c1+1)&1;i<=c2;i++,cur^=1){
            f[cur][0]=f[cur^1][1]+f[cur^1][0];
            f[cur][1]=f[cur^1][2]+f[cur^1][1];
            f[cur][2]=f[cur^1][0]+f[cur^1][2];
        }
        return f[(c1+c2)&1][0]%mod;
    }

    inline int main(){
        File(or.in,or.out);
        n=read(),t=read(); init();
        for(int i=0;i<=log2(t);i++) if(t>>i&1) i&1?cnt2++:cnt1++;
        for(int i=cnt1+cnt2,base=1;i>=0;i--,base=-base){
            int res=0;
            for(int j=max(i-cnt2,0);j<=cnt1;j++){
                int k=i-j;
                if(k<0) break;
                res=(res+C(cnt1,j)*C(cnt2,k)%mod*qpow(calc(j,k),n)%mod)%mod;
            }
            ans=(ans+base*res+mod)%mod;
        }
        printf("%lld\n",ans);
        return 0;
    }
}
signed main(){return CL::main();}

B.最短路径

考虑 k 个关键点的最短路径是什么样的

发现若回到起点，那么路径长度就是这 k 个点的虚树的边长度之和 \times 2 再减去虚树的最长链

那么所求的期望就可以转化为求虚树边长之和的期望和虚树直径的期望

首先考虑求虚树边长之和的期望

若一条边对答案有贡献，那么这条边的两边一定分别有一些关键点，但是这个不大好求，就可以用总方案数减去不合法的方案数

不合法的方案数就是所有关键点全在这条边的一侧的方案数，\text{DFS} 一遍就能算出来

接着考虑求虚树直径的期望

由于 m\leq 300 可以考虑暴力一点的方法

直接钦定 (u,v) 为虚树的直径，当且仅当 \texttt{dis}(u,v) 最大且 u,v 字典序最小

枚举 u,v 和要加入这棵虚树的点 w，发现 w 能加入当且仅当以下条件均不满足：

统计出满足条件的 w 的数量乘上组合数系数即可

时间复杂度 O(m^3)

#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned long long
#define fir first
#define sec second
using namespace std;
namespace IO{
    #define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout);
    #define fill(a,b,c,d) memset(a,b,sizeof(c)*(d+1))
    #define copy(a,b,c,d) memcpy(a,b,sizeof(c)*(d+1))
    #define fillall(x,y) memset(x,y,sizeof(x))
    #define copyall(x,y) memcpy(x,y,sizeof(x))
    inline int read(){
        int w=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
        while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
        return w*f;
    }
}
using namespace IO;
namespace CL{

    const int maxn=2e3+5,maxm=305,mod=998244353;

    int n,m,K; ll ans;
    int cur[maxn],dep[maxn],size[maxn],dis[maxm][maxm];
    ll fac[maxm],inv[maxm];
    bool is[maxn];
    namespace Graph{
        int head[maxn],id;
        struct e{int v,next;}edge[maxn<<1];
        inline void add(int u,int v){
            edge[++id]=(e){v,head[u]};
            head[u]=id;
        }
    }using namespace Graph;
    inline ll qpow(ll x,ll y){
        ll res=1;
        for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
        return res;
    }
    inline ll C(ll n,ll m){
        if(m>n) return 0;
        return fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    inline void init(){
        fac[0]=inv[0]=1;
        for(int i=1;i<=300;i++) fac[i]=fac[i-1]*i%mod;
        inv[300]=qpow(fac[300],mod-2);
        for(int i=299;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    }
    void dfs1(int u,int fa){
        dep[u]=dep[fa]+1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v;
            if(v!=fa) dfs1(v,u);
        }
    }
    void dfs2(int u,int fa){
        if(is[u]) size[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v;
            if(v==fa) continue;
            dfs2(v,u);
            size[u]+=size[v];
        }
        ans=(ans+2ll*(C(m,K)-C(size[u],K)-C(m-size[u],K)+2ll*mod)%mod)%mod;
    }

    inline int main(){
        File(tree.in,tree.out);
        n=read(),m=read(),K=read(); 
        init();
        for(int i=1;i<=m;i++) is[cur[i]=read()]=1;
        for(int i=1;i<n;i++){
            int x=read(),y=read();
            add(x,y),add(y,x);
        }
        for(int i=1;i<=m;i++){
            dfs1(cur[i],0);
            for(int j=1;j<=m;j++) dis[i][j]=dep[cur[j]]-dep[cur[i]];
        }
        dfs2(1,0);
        for(int i=1;i<=m;i++)
            for(int j=i+1;j<=m;j++){
                int cnt=0;
                for(int k=1;k<=m;k++){
                    if(k==i || k==j) continue;
                    if(dis[i][k]>dis[i][j] || (dis[i][k]==dis[i][j] && k<j)) continue;
                    if(dis[j][k]>dis[i][j] || (dis[j][k]==dis[i][j] && k<i)) continue;
                    cnt++; 
                }
                ans=(ans-C(cnt,K-2)*dis[i][j]%mod+mod)%mod;
            }
        printf("%lld\n",ans*qpow(C(m,K),mod-2)%mod);
        return 0;
    }
}
signed main(){return CL::main();}

C.仙人掌

仙人掌，我不会，咕咕咕

D.对弈

手玩不难发现 \texttt{Alice} 一定向右移动棋子，\texttt{Bob} 一定向左移动棋子

设 a_i 为第 i 个红棋子的位置，b_i 为第 i 个蓝棋子的位置，d_i=b_i-a_i

那么这就相当于一共有 \frac{k}{2} 堆石子，第 i 堆的石子个数为 d_i，每次可以选至少 1 堆，至多 m 堆石子，从这几堆中各取走若干石子，每堆至少取一个

这就是一种 \text{K-Nim} 游戏，有结论：

先手必败，当且仅当将所有 d_i 转成二进制后，每一位 1 的个数 \pmod{m+1}=0

证明：

设 f_{i,j} 为考虑到二进制第 i 位，已经拿了 j 个石子先手必败的方案数，有：

f_{i,j}\gets f_{i-1,j-2^ix(m+1)}\times\binom{\frac{k}{2}}{x(m+1)}

这个可以写一个记忆化搜索

最后枚举石子总数，有：

\sum\limits_{i=0}^{n-k}f_{20,i}\times\binom{n-\frac{k}{2}-i}{\frac{k}{2}}

组合数考虑插板法，对于经典问题将 n 分成 m 个正整数的方案数为 \binom{n-1}{m-1}

由于枚举的是石子总数，那么剩下的 n-\frac{k}{2}-i 要分给 \frac{k}{2}+1 个空

而这 \frac{k}{2}+1 个空的要求非负，所以插板中的空要再加上 \frac{k}{2}

时间复杂度 O(nk)

#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned long long
#define fir first
#define sec second
#define int long long 
using namespace std;
namespace IO{
    #define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout);
    #define fill(a,b,c,d) memset(a,b,sizeof(c)*(d+1))
    #define copy(a,b,c,d) memcpy(a,b,sizeof(c)*(d+1))
    #define fillall(x,y) memset(x,y,sizeof(x))
    #define copyall(x,y) memcpy(x,y,sizeof(x))
    inline int read(){
        int w=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
        while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
        return w*f;
    }
}
using namespace IO;
namespace CL{

    const int maxn=1e4+5,mod=1e9+7;

    int n,K,m,ans;
    int fac[maxn],inv[maxn],f[21][maxn];
    inline int qpow(int x,int y){
        int res=1;
        for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
        return res;
    }
    inline int C(int n,int m){
        if(m>n) return 0;
        return fac[n]*inv[m]%mod*inv[n-m]%mod; 
    }
    inline void init(){
        fac[0]=inv[0]=1;
        for(int i=1;i<=10000;i++) fac[i]=fac[i-1]*i%mod;
        inv[10000]=qpow(fac[10000],mod-2);
        for(int i=9999;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    }
    int dfs(int pos,int num){
        if(~f[pos][num]) return f[pos][num];
        if(!pos && !num) return f[pos][num]=1;
        if(!pos) return f[pos][num]=0;
        int res=0;
        for(int i=0;i<=K;i+=m+1){
            int tmp=(1<<pos-1)*i;
            if(tmp>num) break;
            res=(res+dfs(pos-1,num-tmp)*C(K,i)%mod)%mod;
        }
        return f[pos][num]=res;
    }

    inline int main(){
        File(chess.in,chess.out);
        n=read(),K=read()/2,m=read(); init();
        fillall(f,-1);
        for(int i=0;i<=n-2*K;i++) ans=(ans+dfs(20,i)*C(n-K-i,K)%mod)%mod;
        printf("%lld\n",(C(n,2*K)-ans+mod)%mod);
        return 0;
    }
}
signed main(){return CL::main();}