周赛Round30

D.小红整数操作

首先一个很显然的思路是算出满足大于等于l的最小的x需要乘几，再算出满足小于等于r的最大的y需要乘几，然后这两个数之差就能得到有几组可行的x,y。开始就是这样写的，但是挂了 因为问题是这个思路默认了x,y开始都小于l,r，但这是不一定的。在赛场上意识到这个问题后我一度想分类讨论x,y和l,r的大小关系，但情况太多，显然也是不可行的。 其实仔细看一下，我们除了乘a之外，还可以除a，那我们完全可以先把x,y除到最小，再开始乘，就可以按上面的思路来了，而除到最小需要除gcd(x,y)。

void solve(void){ 
	int x,y,l,r,low,up;
	cin>>x>>y>>l>>r;
    if(x>y)swap(x,y);
	int d=__gcd(x,y);
    x/=d;
    y/=d;
    int mn=l/x;
    if(l%x)mn++;
    int mx=r/y;
    if(mx>=mn)cout<<mx-mn+1;
    else cout<<0;
}

E.小红树上染色

树形dp，没什么好说的，和 没有上司的舞会 很像，不能有相邻的白色节点，那么如果当前根节点为白色，所有儿子都必须为红，如果根节点为红，儿子可以为白也可以为红。 但是得到了一个惨痛的教训：%的优先级比*/低，但是比+-高，所以a*b%mod是可以的，但是a+b%mod是不行的，必须写成(a+b)%mod

__int128 cnt[N][2];
void dfs(int u,int f){
	cnt[u][0]=1;
	cnt[u][1]=1;
	for(int v:a[u]){
		if(v==f)continue;
		dfs(v,u);
		cnt[u][0]=cnt[u][0]*cnt[v][1]%mod;
		cnt[u][1]=cnt[u][1]*(cnt[v][1]+cnt[v][0])%mod;
	}
//	cout<<u<<' '<<cnt[u][0]<<' '<<cnt[u][1]<<'\n';
}
void solve(void){ 
	int n;
	cin>>n;
	rep(i,1,n-1) {
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs(1,0);
	write((cnt[1][0]+cnt[1][1])%mod);
}

F.小红又又又战小紫

概率dp,需要注意的关键是这是从末态往初态推的，并且每一次转移轮数都要加一。具体来说，dp(i,j)表示小红有i张一攻卡，小紫有j张一攻卡时，剩余轮数的期望，此时如果小红抽到一攻卡，小紫抽到二攻卡，小紫的卡会干掉小红的卡，会转移到dp(i-1,j)，如果小紫抽到一攻，小红抽到二攻，会转移到dp(i,j-1)，如果抽到卡攻击相等，还会转移到dp(i,j)，因此有

dp(i,j)=(1-p2-p3)*dp(i,j)+p2*dp(i-1,j)+p3*dp(i,j-1)+1

整理得

dp(i,j)=(p2*dp(i-1,j)+p3*dp(i,j-1)+1)/(p2+p3)

具体实现时还需要注意，每进行一步操作，都要取模，并且对于除法需要使用乘法逆元。

    cin>>n>>m;
    int cnt[2][3]={0};
    int dp[55][55]={0};
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        cnt[0][t]++;
    }
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        cnt[1][t]++;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            int p2=i*inv(i+cnt[0][2])%mod*(cnt[1][2]*inv(j+cnt[1][2])%mod)%mod;
            int p3=cnt[0][2]*inv(i+cnt[0][2])%mod*(j*inv(j+cnt[1][2])%mod)%mod;
            dp[i][j]=(p2*dp[i-1][j]%mod+p3*dp[i][j-1]%mod+1)%mod*inv(p2+p3)%mod;
        }
    cout<<dp[cnt[0][1]][cnt[1][1]];