ARC162 简要题解

syzf2222 · 2023-06-19 14:47:02 · 个人记录

ABC 没做。

D. Smallest Vertices

对每个点算贡献。首先生成树的数量为 \dfrac{(n-2)!}{\prod d_i!}d_{rt}。

那么对于一个点 i，钦定集合 S 在其子树中，需要满足 \sum\limits_{x\in S} d_x=|S|-1，这样的生成树数量为 \dfrac{(|S|-2)!}{\prod\limits_{x\in S}d_x!}d_i\dfrac{(n-|S|-1)!}{\prod\limits_{x\notin S}d_x!}d_1，你发现它与 S 无关。于是直接 dp 出 S 的数量然后算贡献即可。特殊处理根和叶子。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int N=505;
int n,m,fac[N],inv[N],ifc[N],ans,d[N],dp[N][N],kk=1;
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int main(){
    n=read();fac[0]=ifc[0]=inv[1]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*i*fac[i-1]%mod;
    for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
    for(int i=1;i<=n;i++)d[i]=read(),kk=1ll*kk*ifc[d[i]]%mod;
    kk=1ll*kk*d[1]%mod;ans=1ll*kk*fac[n-2]%mod;dp[0][0]=1;
    for(int i=n;i>=2;i--){
        if(!d[i])ans=(ans+1ll*kk*fac[n-2])%mod;
        else for(int j=2;j<=n-i+1;j++)if(j-d[i]>0)
            ans=(ans+1ll*dp[j-1][j-1-d[i]]*kk%mod*fac[j-2]%mod*fac[n-j-1]%mod*d[i])%mod;
        for(int j=n-i+1;j>=0;j--)
            for(int k=n-d[i];k>=0;k--)
                add(dp[j+1][k+d[i]],dp[j][k]);
    }printf("%d\n",ans);
    return 0;
}

E. Strange Constraints

挺有意思的题，反正比 F 优美不少。

首先 A 是集合，所以不妨将 A 排序。这时要放若干种数，若一种数要放 x 个，则它只能放在一个后缀中，而且也只能匹配一个后缀。注意到这都是后缀，于是我们直接从大往小 dp 出现次数就可以方便地计算答案。

这时你写出来发现算重了，是因为如果出现次数相同则两者完全等价，需要除以阶乘。但是关注到出现次数为 x 只能有 \frac nx 个，于是复杂度为 \sum\limits_{i=1}^n n(\frac ni)^2=O(n^3)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int N=505;
int n,m,a[N],c[N],dp[2][N][N],S[N][N],C[N][N],ans,inv[N],ifc[N],fac[N];
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int main(){
    n=read();inv[1]=fac[0]=ifc[0]=1;
    for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=1;i<=n;i++)ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }for(int i=1;i<=n;i++)
        a[i]=read(),c[a[i]]++;
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--)c[i]+=c[i+1];
    dp[(n+1)&1][0][0]=1;
    for(int i=n;i>=1;i--){
        int o=(i&1);
        memset(dp[o],0,sizeof(dp[o]));
        int Mx=n/i;
        for(int j=0;j<=Mx;j++)
            for(int k=0;k<=n;k++){
                int v=dp[o^1][j][k],kk=1;
                add(dp[o][j][k],v);
                for(int p=1;k+p*i<=min(n,c[i])&&j+p<=min(n,1+c[i]);p++){
                    kk=1ll*kk*max(0,c[i]-j-p+1)%mod*C[c[i]-k-(p-1)*i][i]%mod;
                    add(dp[o][j+p][k+p*i],1ll*kk*v%mod*ifc[p]%mod);
                }
            }
    }for(int i=1;i<=n;i++)ans=(ans+dp[1][i][n])%mod;
    printf("%d\n",ans);
    return 0;
}

F. Montage

弱智题，不知道为什么放 F，不知道为什么评大红。

首先由于我的个人问题，不妨反转一下条件的符号，其实也就是把矩阵反过来看。

我们注意到 1 的分布一定形如这种：

图不是很典型，大概意会一下就能体会到。

我们 dp 上沿的轮廓线，可以往右走或者往下走，往下走时可以继承一个不大于上面的长度。具体细节不难编。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
inline int Add(int x){return x>=mod?x-mod:x;}
const int N=405;
int n,m,f[N][N][N],g[N][N][N],ans,S[N];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)f[i][0][0]=1;
    for(int j=1;j<=m;j++){
        for(int k=0;k<=m;k++)S[k]=0;
        int tot=0;
        for(int i=1;i<=n;i++){
            int sum=0;add(f[i][j][1],tot);
            for(int k=m;k>=0;k--){
                if(k){
                    add(f[i][j][k],Add(f[i][j-1][k-1]+g[i][j-1][k-1]));
                    add(f[i][j][k],S[k]);
                }g[i][j][k]=Add(f[i][j-1][k]+g[i][j-1][k]);
                add(sum,f[i][j][k]);add(S[k],sum);
                if(k)add(tot,g[i][j][k]);
            }add(ans,sum);
        }
    }printf("%d\n",ans+1);
    return 0;
}

深深地感到自己的弱小。