CSP模拟12

yszy / 2023-08-03 / 原文

跟DP专题似的而且啥都套个概率期望……寄！

随

打表log的式子 $ \frac{ (n-1) ( n^{m} - (n-2)^m ) }{n^{m}} $

根据生成函数/差分证明了正确性！

便

Code

没调出来

A

直接码式子

Code

#include<cstdio>

#define int long long

using namespace std;
const int N=205;
const int inf=-1e15;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int max(int a,int b){
    return a>b?a:b;
}

int ksm(int a,int b){
    int ans=1;

    while(b){
        if(b&1)
            ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}

int n,m,R,P;
int typ[N],val[25];
int dp[N][N][15][25];

int calc(int x,int k){
    return ksm(P,x-1)*val[k];
}

void work(int l,int r){
    dp[l][r][1][typ[l]]=max(dp[l][r][1][typ[l]],dp[l+1][r][0][0]);
    dp[l][r][1][typ[r]]=max(dp[l][r][1][typ[r]],dp[l][r-1][0][0]);

    for(int x=1;x<=R;x++){
        for(int k=1;k<=m;k++){
            for(int i=l;i<=r-1;i++){
                dp[l][r][x][k]=max(dp[l][r][x][k],dp[l][i][x-1][k]+dp[i+1][r][x-1][k]);
            }
        }
    }

    for(int i=l;i<=r-1;i++){
        dp[l][r][0][0]=max(dp[l][r][0][0],dp[l][i][0][0]+dp[i+1][r][0][0]);
    }
    
    for(int x=1;x<=R;x++){
        for(int k=1;k<=m;k++){
            dp[l][r][0][0]=max(dp[l][r][0][0],dp[l][r][x][k]+calc(x,k));
        }
    }
}

signed main(){
    n=read(),m=read(),R=read(),P=read();

    for(int i=1;i<=n;i++)
        typ[i]=read();
    for(int i=1;i<=m;i++)
        val[i]=read();
    
    for(int l=1;l<=n;l++){
        for(int r=1;r<=n;r++){
            for(int x=0;x<=R;x++){
                for(int k=0;k<=m;k++){
                    if(l==r){
                        if(x==0&&k==0){
                            dp[l][r][x][k]=val[typ[l]];
                        }else if(x==1&&k==typ[l]){
                            dp[l][r][x][k]=0;
                        }else{
                            dp[l][r][x][k]=inf;
                        }
                    }else{
                        dp[l][r][x][k]=inf;
                    }
                }
            }
        }
    }

    for(int len=1;len<=n;len++){
        for(int l=1;l<=n-len+1;l++){
            work(l,l+len-1);
        }
    }

    printf("%lld",dp[1][n][0][0]);

    return 0;
}

C

SG[u]=(SG[v1]+1)+(SG[v2]+1)……
证明
要求每一个点就直接换根。

Code

#include<cstdio>
#include<cstring>

#define ll long long

using namespace std;
const int N=1e6+5;
const int mod=1e9+7;

int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll ksm(int a,int b){
    ll ans=1;

    while(b){
        if(b&1)
            ans=ans*1ll*a%mod;
        a=1ll*a*1ll*a%mod;
        b>>=1;
    }
    return ans;
}

struct Node{
    int to,next;
}e[N<<1];
int lk[N],ntot;

void add(int x,int y){
    e[++ntot]=(Node){y,lk[x]};
    lk[x]=ntot;
}

int T;
int dp1[N],dp2[N];
int n;

void dfs1(int x,int fa){
    for(int i=lk[x];i;i=e[i].next){
        int y=e[i].to;

        if(y==fa)
            continue;
        dfs1(y,x);

        dp1[x]^=(dp1[y]+1);
    }
}

void dfs2(int x,int fa){
    for(int i=lk[x];i;i=e[i].next){
        int y=e[i].to;

        if(y==fa)
            continue;
        dp2[y]=dp1[y]^((dp2[x]^(dp1[y]+1))+1);
        dfs2(y,x);
    }
}

void clear(){
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    memset(lk,0,sizeof(lk));
    memset(e,0,sizeof(e));
    ntot=0;
}

signed main(){
    T=read();

    while(T--){
        clear();
        n=read();

        for(int i=1;i<=n-1;i++){
            int x=read(),y=read();

            add(x,y),add(y,x);
        }

        dfs1(1,0);
        dp2[1]=dp1[1];
        // printf("%lld \n",dp1[1]);
        dfs2(1,0);

        ll cnt=0;

        for(int i=1;i<=n;i++){
            if(dp2[i]){
                cnt++;
                cnt%=mod;
            }
        }
        printf("%lld \n",cnt);
        printf("%lld \n",cnt*ksm(n,mod-2)%mod);
    }

    return 0;
}

---