2021牛客暑期多校训练营9 部分题题解

2024-01-06 21:06:34

C.Cells

题目链接

简要题解

这个题首先需要用到LGV引理，引理的具体内容此处不加讨论。
我们根据LGV引理得到，所要求的答案就是下面那个行列式：

朴素的行列式求值是利用高斯消元，但是显然在这里不适用，于是我们要进行更多的推导。
进行一步转置操作，答案不变。

\[\left| \begin{array}{cccc} C_{a_1+1}^1 & C_{a_1+2}^2 & \cdots & C_{a_1+n}^n \\ C_{a_2+1}^1 & C_{a_2+2}^2 & \cdots & C_{a_2+n}^n \\ \vdots & \vdots & \ddots & \vdots \\ C_{a_n+1}^1 & C_{a_n+2}^2 & \cdots & C_{a_n+n}^n \\ \end{array} \right|= \left| \begin{array}{cccc} C_{a_1+1}^1 & C_{a_2+1}^1 & \cdots & C_{a_n+1}^1 \\ C_{a_1+2}^1 & C_{a_2+2}^2 & \cdots & C_{a_n+2}^2 \\ \vdots & \vdots & \ddots & \vdots \\ C_{a_1+n}^n & C_{a_2+n}^n & \cdots & C_{a_n+n}^n \\ \end{array} \right| \]

我们拆掉组合数，把分母的阶乘提出来，得到

\[\prod_{i=1}^n\frac{1}{i!}\left| \begin{array}{cccc} \frac{(a_1+1)!}{a_1!} & \frac{(a_2+1)!}{a_2!} & \cdots & \frac{(a_n+1)!}{a_n!} \\ \frac{(a_1+2)!}{a_1!} & \frac{(a_2+2)!}{a_2!} & \cdots & \frac{(a_n+2)!}{a_n!} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{(a_1+n)!}{a_1!} & \frac{(a_2+n)!}{a_2!} & \cdots & \frac{(a_n+n)!}{a_n!} \\ \end{array} \right| \]

我们对这个行列式进行初等行变换，那么我们可以得到

\[\prod_{i=1}^n\frac{a_i+1}{i!}\left| \begin{array}{cccc} 1 & 1 & \cdots & 1 \\ (a_1+1) & (a_2+1) & \cdots & (a_n+1) \\ \vdots & \vdots & \ddots & \vdots \\ (a_1+1)^{n-1} & (a_2+1)^{n-1} & \cdots & (a_n+1)^{n-1} \\ \end{array} \right| \]

具体怎么进行初等行变换呢，拿三行一列来举个例子：

\[\left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)*（a_1+2） \\ (a_1+1)*(a_1+2)*(a_1+3)\\ \end{array} \right|\Rightarrow \left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)*（a_1+2） \\ (a_1+1)^2*(a_1+2)\\ \end{array} \right|\Rightarrow \left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)^2 \\ (a_1+1)^2*(a_1+2)\\ \end{array} \right|\Rightarrow \left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)^2 \\ (a_1+1)^3\\ \end{array} \right| \]

右边那个是范德蒙行列式，它的值$$D_n=\prod_{1\leq j<i\leq n}((a_i+1)-(a_j+1))$$
这个东西可以构造多项式求解，我们令$f(x)=\sum_{i=1}^{n}x^{a_i}$，$g(x)=\sum_{i=1}^nx^{-a_i}$
用$NTT$对$f(x)$和$g(x)$做卷积，那么$x$的指数就是$a_i-a_j$，系数就是满足$a_i-a_j$的$(i,j)$对数。
设$h(x)=f(x)*g(x)=\sum_{i=1}^{\infty}H_i*x^i$，那么$D_n=\prod_{i=1}^{\infty}i^{H_i}$
我们对$D_n$取模时，讲道理$H_i$要对$998244352$取模，但是观察发现$H_i$不可能超过模数，所以可以直接$NTT$
时间复杂度$O(n*logn)$
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
const int Mod=998244353;
int n,m,Ans,Seq[MAXN],Fac[MAXN],Inv[MAXN];
int Read()
{   int a=0,c=1;   char b=getchar();
    while(b!='-'&&(b<'0'||b>'9')) b=getchar();
    if(b=='-') c=-1,b=getchar();
    while(b>='0'&&b<='9') a=a*10+b-48,b=getchar();
    return a*c;
}
int Pow(int Base,int P)
{   int Ret=1,Cnt=Base;
    for(;P>=1;P>>=1) P&1?Ret=1ll*Ret*Cnt%Mod:0,Cnt=1ll*Cnt*Cnt%Mod;
    return Ret;
}
int Add(int A,int B){   return A+=B,A>=Mod?A-Mod:A;   }
namespace Poly
{   int Len,Ms,Inv,Rader[1<<21],A[1<<21],B[1<<21];
    void NTT(int *P,int K)
    {   for(int i=0;i<Len;i++)
            if(i<Rader[i]) swap(P[i],P[Rader[i]]);
        for(int i=1;i<Len;i<<=1)
        {   int Euler=Pow(3,(Mod-1)/(i<<1));
            if(K<0) Euler=Pow(Euler,Mod-2);
            for(int Pos=(i<<1),j=0;j<Len;j+=Pos)
            {   int Wi=1;
                for(int k=0;k<i;k++,Wi=1ll*Wi*Euler%Mod)
                {   int X=P[j+k],Y=1ll*Wi*P[i+j+k]%Mod;
                    P[j+k]=Add(X,Y),P[i+j+k]=Add(X,Mod-Y);
                }
            }
        }
        if(K>0) return ;
        Inv=Pow(Len,Mod-2);
        for(int i=0;i<Len;i++) P[i]=1ll*P[i]*Inv%Mod;
    }
    void Prepare(int Lx)
    {   Ms=-1;
        for(Len=1;Len<=Lx;Len<<=1) Ms++;
        for(int i=0;i<Len;i++) Rader[i]=(Rader[i>>1]>>1)|((i&1)<<Ms);
    }
    void Work()
    {   for(int i=1;i<=n;i++) A[Seq[i]]++,B[1000001-Seq[i]]++;
        Prepare(2e6),NTT(A,1),NTT(B,1);
        for(int i=0;i<Len;i++) A[i]=1ll*A[i]*B[i]%Mod;
        NTT(A,-1);
    }
}using Poly::Work;using Poly::A;
int main()
{   n=Read(),Fac[0]=Ans=1;
    for(int i=1;i<=n;i++) Seq[i]=Read(),Fac[i]=1ll*Fac[i-1]*i%Mod;
    Inv[n]=Pow(Fac[n],Mod-2);
    for(int i=n-1;i>=0;i--) Inv[i]=1ll*Inv[i+1]*(i+1)%Mod;
    for(int i=1;i<=n;i++) Ans=1ll*Ans*(Seq[i]+1)%Mod*Inv[i]%Mod;
    Work();
    for(int i=1000002;i<=2000001;i++) Ans=1ll*Ans*Pow(i-1000001,A[i])%Mod;
    printf("%d\n",Ans);
}

I.Incentive Model

题目链接

Incentive Model

简要题解

题目的大意是，$A$和$B$两个人依次争夺$n$块区域，两人分别有个初始能力值$a$和$b$。
对于每一块区域的争夺，$A$获胜的概率为$\frac{a}{a+b}$，$B$获胜的概率为$\frac{b}{a+b}$，获胜的一方将会增加$w$点能力值。
求最终$A$获胜的期望次数。

考场上大部分人没读懂题，这个可以直接做。
我们设$E(x)$表示，已经争夺了$x$块区域，$A$的期望能力值，那么不难写出转移方程：

\[E(x+1)=E(x)+\frac{E(x)}{1+w*x}w \]

\[E(x+1)=\frac{1+(w+1)*x}{1+w*x}E(x) \]

\[\frac{E(x+1)}{1+(w+1)*x}=\frac{E(x)}{1+w*x} \]

于是我们得到

\[\frac{E(x)}{1+w*x}=\frac{E(0)}{1}=a \]

\[E(x)=a+a*x*w \]

由于总能力值等于初始能力值加上后面获胜取得的能力值，我们令$x=n$，就能发现$$Ans=a*n$$
直接输出即可。
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int Mod=998244353;
int n,W,X,Y;
int Pow(int B,int P)
{   int Ret=1,Cnt=B;
    while(P>=1) P&1?Ret=1ll*Ret*Cnt%Mod:0,Cnt=1ll*Cnt*Cnt%Mod,P>>=1;
    return Ret;
}
int main()
{   scanf("%d%d%d%d",&n,&W,&X,&Y);
    printf("%lld\n",1ll*X*Pow(Y,Mod-2)%Mod*n%Mod);
}

J.Jam

题目链接

Jam

简要题解

由于道路不是很多，我们可以手动把情况全部枚举出来。
可以发现，对于右转的车辆，不会与任何车道的车冲突，于是右转的灯可以一直亮着。
剩下了$12$条车道，我们经过手玩可以发现，每一秒钟，最多同时亮两个绿灯，我们还可以求出能够在同一秒亮绿灯的所有车道对。
既然要时间最短，我们肯定希望同时亮两个绿灯的次数最多，这就变成了一个求最大匹配的问题。
解决方法比较多，这里介绍一种网络流建图跑最大流的做法。

既然要求匹配，我们就把每个车道拆成两个点，放在左右两排，还有源点$S$和汇点$T$。
左边一排点和$S$连边，右边一排点和$T$连边，流量为对应车道的车辆数。
两排点之间，能够匹配的就连边，注意同一车道的两个点不能连边，因为这不是一组合法的匹配。
跑出来的最大流除以$2$，就是最大匹配数了。

为什么要除以$2$？我们建图跑出来的最大流并不是真正的匹配数，一个车道对应了两个点。
对于一组匹配$(a,b)$来说，可以是左边的$a$匹配右边的$b$，也可以是右边的$a$匹配左边的$b$。
但是我们得到的是最大流，感性理解，最优方案一定是最优匹配正反各做一次。
换句话说，如果在真正的最大匹配中，$(a,b)$是其中的一组匹配，那么在我们建的图中，左右匹配两次肯定最优。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int Ts,Ans,Car[200],Cp[200][3];
int Seq[200]={2,3,7,8,9,12,13,14};
void Init()
{   Cp[2][0]=3,Cp[2][1]=12,Cp[2][2]=14;
    Cp[3][0]=2,Cp[3][1]=7,Cp[3][2]=9;
    Cp[7][0]=3,Cp[7][1]=8,Cp[7][2]=13;
    Cp[8][0]=7,Cp[8][1]=12,Cp[8][2]=14;
    Cp[9][0]=3,Cp[9][1]=12,Cp[9][2]=13;
    Cp[12][0]=2,Cp[12][1]=8,Cp[12][2]=9;
    Cp[13][0]=7,Cp[13][1]=9,Cp[13][2]=14;
    Cp[14][0]=2,Cp[14][1]=8,Cp[14][2]=13;
}
int Max(int A,int B){   return A>B?A:B;   }
int Min(int A,int B){   return A<B?A:B;   }
namespace Net
{   struct EDGE{   int u,v,w,Next;   }Edge[100010];
    int S,T,Es,First[100],Deep[100],Vis[100],Cur[100];
    queue<int>Team;
    void Link(int u,int v,int w){   Edge[++Es]=(EDGE){u,v,w,First[u]},First[u]=Es;   }
    int Bfs()
    {   for(int i=S;i<=T;i++) Vis[i]=Deep[i]=0;
        Team.push(S),Deep[S]=1,Vis[S]=1;
        while(!Team.empty())
        {   int k=Team.front();   Team.pop();
            for(int i=First[k];i!=-1;i=Edge[i].Next)
            {   int v=Edge[i].v;
                if(Vis[v]||!Edge[i].w) continue ;
                Vis[v]=1,Deep[v]=Deep[k]+1,Team.push(v);
             }
        }
        return Deep[T];
    }
    int Dinic(int Pos,int Mins)
    {   if(Pos==T) return Mins;
        for(int &i=Cur[Pos];i!=-1;i=Edge[i].Next)
        {   int v=Edge[i].v;
            if(Deep[v]!=Deep[Pos]+1||!Edge[i].w) continue ;
            int X=Dinic(v,Min(Mins,Edge[i].w));
            if(X) return Edge[i].w-=X,Edge[i^1].w+=X,X;
        }
        return 0;
    }
    void Work()
    {   while(Bfs())
        {   for(int i=S;i<=T;i++) Cur[i]=First[i];
            while(int Nv=Dinic(S,1e9)) Ans-=Nv;
        }
    }
    void Build()
    {   Es=-1,S=0,T=33;
        for(int i=0;i<=T;i++) First[i]=-1;
        for(int i=0;i<=7;i++)
        {   Link(S,Seq[i],Car[Seq[i]]),Link(Seq[i],S,0);
            Link(Seq[i]+16,T,Car[Seq[i]]),Link(T,Seq[i]+16,0);
            for(int j=0;j<=2;j++)
            {   int u=Seq[i],v=Cp[u][j];
                Link(u,v+16,1e9),Link(v+16,u,0);
            }
        }
    }
}using namespace Net;
int main()
{   Init();
    for(scanf("%d",&Ts);Ts;Ts--)
    {   for(int i=1;i<=16;i++) scanf("%d",&Car[i]);
        Build(),Work(),Ans/=2;
        for(int i=0;i<=7;i++) Ans+=Car[Seq[i]];
        printf("%d\n",Max(Ans,Max(Car[4],Max(Car[5],Max(Car[10],Car[15]))))),Ans=0;
    }
}

码农公寓

C.Cells

题目链接

简要题解

I.Incentive Model

题目链接

简要题解

J.Jam

题目链接

简要题解

相关文章