《小白月赛25》部分题解

D：
思路：概率论.
计算出每个卡池拿不到的概率,最后1-即可.
注意1-之后可能会<0,所以要加上模数再取模.
这里的概率计算直接上逆元就可以了.
小细节:ma *= a%mod,是不对的这样本质上是先对a取模再乘ma.这样存在爆精度的问题.
Code:

LL quick(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = (re*a)%Mod;
        b >>= 1;
        a = (a*a)%Mod;
    }
    return re;
}
LL a[N],b[N];
int main()
{
    int n;sd(n);
    for(int i=1;i<=n;++i) sld(a[i]);
    for(int i=1;i<=n;++i) sld(b[i]);
    LL ma = 1;
    for(int i=1;i<=n;++i)
    {
        ma = ma*(a[i]-b[i])%Mod;
        ma = ma*quick(a[i],Mod-2)%Mod;
    }
    printf("%lld\n",(Mod+(1-ma))%Mod);
    system("pause");
    return 0;
}

G：
思路：
很显然这个函数是个单调递增函数.
那么可以直接二分。精度需要扣的比较准,直接循环二分,循环次数开稍微大点。
注意：边界L应该为-INF,因为x可能为负数.二分时按照L = mid,r = mid来,L = mid+1会导致精度丢失..
Code:

double eps = 1e-8;
double a,b,c;
bool cal(double x)
{
    double ma = 1;
    for(int i=1;i<=a;++i) ma *= x;
    ma += b*log(x);
    if(ma-c <= eps) return 1;
    return 0;
}
int main()
{
    cin >> a >> b >> c;
    double L = -INF,r = INF,ans = -INF;
    for(int i=1;i<=1000;++i)
    {
        double mid = (L+r)/2;
        if(cal(mid)) 
        {
            ans = mid;
            L = mid;
        }  
        else r = mid;
    }
    if(ans == -INF) printf("-1\n");
    else printf("%.8f\n",ans);
    //system("pause");
    return 0;
}

J:
思路：位运算。
统计每个二进制位的1和0的个数.
显然,能使这个二进制位不为0的三元组选法只有1 1 1和1 0 0.
然后就能判断了。
注意点:slove函数难以实现对0的个数统计,因为如果初始为0,直接就退出.
所以可以只统计1的个数,然后剩下的0的个数就是n-num1.
Code:

LL a[N],b[61];//1
void slove(LL x)
{
    for(int i=0;x;++i)
    {
        int ma = x%2;
        if(ma&1) b[i]++;
        x /= 2;
    }
}
LL quick_mi(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = (re*a)%Mod;
        b >>= 1;
        a = (a*a)%Mod;
    }
    return re;
}
LL C(LL n,LL m)
{
    LL re = 1;
    for(int i=1;i<=m;++i) 
    {
        re = re*1LL*(n-i+1)%Mod;
        re = re*quick_mi(i,Mod-2)%Mod;
    }
    return re;
}
int main()
{
    int n;sd(n);
    for(int i=1;i<=n;++i) 
    {
        sld(a[i]);
        slove(a[i]);
    }
    LL ans = 0;
    for(int i=0;i<=63;++i)
    {
        if(b[i] >= 3) 
        {
            LL ma = (1LL<<i)%Mod*C(b[i],3)%Mod;
            ans = (ans+ma)%Mod;
        }
        if(b[i] >= 1 && b[i] >= 2)
        {
            LL ma = (1LL<<i)%Mod*b[i]%Mod*C(n-b[i],2)%Mod;
            ans = (ans+ma)%Mod;
        }
    }
    plr(ans);
  //  system("pause");
    return 0;
}

C:
思路1：
像兰子姐的题解那样统计白色连通块,并查集合并..然后搞一搞就行了.
思路2：树形dp.
显然对于最后的结果,肯定是要把某个黑染成白更优.
那么定义dp[i][0]为i点向上的白色连通块数量(不包含i),dp[i][1]为i点向下的白色连通块数量(包含i).
显然,如果点u的子节点v为白色,那么dp[u][1] += dp[v][1].
然后再来思考向上的白色怎么求.
首先要向上,肯定保证它的父节点为白***r>那么肯定dp[u][0] += dp[fa][0].
但这很显然是不完全的,因为fa的子节点和fa相连的白色连通块,也是和u相连的(保证fa为白色的前提下)
那么我们再加上dp[fa][1].
这里有了重复,u点往下的数量本身已经被统计在了dp[fa][1]里。所以我们应该减去.
但这里也是有条件的,那就是确保u为白色,因为u不为白色就不会被加在dp[fa][1]里。
Code:

int n,ans = -1,clo[N];//1-白,0-黑
int dp[N][2];//dp[i][0]向上的白色连通块数量(不包含自己),dp[i][1]向下的白色连通块数量(包含自己).
vector<int> G[N];
void dfs1(int u,int fa)
{
    if(clo[u] == 1) dp[u][1] = 1;
    for(auto v:G[u])
    {
        if(v == fa) continue;
        dfs1(v,u);
        if(clo[v] == 1) dp[u][1] += dp[v][1];
    }
}
void dfs2(int u,int fa)
{
    if(clo[fa] == 1)
    {
        dp[u][0] += dp[fa][0];
        dp[u][0] += dp[fa][1];
        if(clo[u] == 1) dp[u][0] -= dp[u][1];
    }
    for(auto v:G[u])
    {
        if(v == fa) continue;
        dfs2(v,u);
    }
    if(clo[u] == 0) ans = max(ans,dp[u][0]+dp[u][1]+1);
    else ans = max(ans,dp[u][0]+dp[u][1]);
}
int main()
{
    sd(n);
    char s[N];scanf("%s",s+1);
    int num = 0;
    for(int i=1;i<=n;++i) clo[i] = (s[i] == 'W');
    for(int i=1;i<=n;++i) if(clo[i] == 1) num++;
    for(int i=1;i<n;++i)
    {
        int x,y;sdd(x,y);
        G[x].pb(y),G[y].pb(x);
    }
    if(num == n) pr(num);
    else
    {
        dfs1(1,0);
        dfs2(1,0);
        pr(ans);
    }
    system("pause");
    return 0;
}

B:
思路：隔板排列.
一开始觉得直接隔板会有重复..
但是其实并不会,因为有b的存在,所以会使所有排列的情况呈现唯一性.
首先对于最终的排列肯定是
a b a b a b ..
或者b a b b a b..的形式.
那么我们开始先隔板求出a的所有排列方式,然后再隔板求出b的所有排列方式.
然后相乘就是这种方式的总方案数.
因为对于每一种的a的排列方式,和每一种b的排列方案组合之后都不会和别的重复。所以是可行的.
分类讨论下即可.
k为偶:
a b a b a b.
C(n-1,k/2-1).
C(m-1,k/2-1).
b a b a b a.
C(n-1,k/2-1).
C(m-1,k/2-1).
k为奇:
a b a b a b a.
C(n-1,k/2).
C(m-1,k/2-1).
b a b a b a b.
C(n-1,k/2-1).
C(m-1,k/2).
*/
Code:

LL f[N];
void init()
{
    f[0] = 1;for(int i=1;i<N;++i) f[i] = f[i-1]*i%Mod;
}
LL quick_mi(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = re*a%Mod;
        b >>= 1;
        a = a*a%Mod;
    }
    return re;
}
LL C(LL n,LL m)
{
    if(n < m) return 0;
    return f[n]*quick_mi(f[m],Mod-2)%Mod*quick_mi(f[n-m],Mod-2)%Mod;
}
int main()
{
    init();
    int n,m,k;sddd(n,m,k);
    if(n+m < k) printf("0\n");
    else
    {
        if(k&1)//奇数
        {
            LL ma1 = C(n-1,k/2)*C(m-1,k/2-1)%Mod;
            LL ma2 = C(n-1,k/2-1)*C(m-1,k/2)%Mod;
            LL ans = (ma1+ma2)%Mod;
            plr(ans);
        }
        else
        {
            LL ans = C(n-1,k/2-1)*C(m-1,k/2-1)%Mod*2%Mod;
            plr(ans);
        }
    }
    system("pause");
    return 0;
}