题解：P17875 [FJCPC 2026] 蛇小弟与奶龙

qianyuzhe · 2026-11-12 18:57:09 · 题解

::::info[这里是原题中的奶龙] ::::

看到奶龙就点进来了，抢到了首 A，你们都不喜欢奶龙吗？

先把概率转成计数，最后除以 \prod\limits_{i=1}^n(a_i+1) 即可。

考虑这个 a_i\oplus b_i 长什么样子。设 C_i=\{a_i\oplus b_i\}，打表可得：

证明类似数位 DP，对 a_i 中的每个 1 当其前缀相同、当前位不同时后面都可以随便取，补上 a_i=b_i 的情况，然后发现不重不漏。

那么我们要在每个 C_i 中取一个 d_i，使得 d_1\oplus\dots\oplus d_n=0。

考虑枚举选过的 d_i 的最高位，设其为 h，那么这个最高位要被选中偶数次。我们把第一个最高位为 h 的 d_i 作为代表元，其低位先不确定，其它 d_i 的低位可以随便取，则代表元的低位也随之固定。除代表元外，最高位为 h 的 d_i 低位有 2^h 种取法；最高位不为 h 的 d_i，设 a_i 截取末 h 位的值为 x，则 d_i 的取法有 x+1 种，因每种最高位 k 都对应 2^k 种选法，补上 0 刚好共有 x+1 种。

那么就可以 DP 了。设 dp_{i,0/1/2} 表示选完 d_1\sim d_i，最高位取过 0 次/最高位取过奇数次/最高位取过非 0 偶数次的方案数，有转移：

边界是：

贡献即为 dp_{n,2}。

别忘了补上所有 d_i 都为 0 的方案。

时间复杂度 \mathcal O(\sum n\log V)。

::::success[代码]{open}

#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
#define N 200005
using namespace std;
int t,n,c,p,i,j,a[N],dp[N][3];
int ksm(int a,int b){
    int r=1;
    while(b){
        if(b&1)r=r*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(c=i=1;i<=n;i++)cin>>a[i];
        for(i=0;i<30;i++){
            p=ksm(2,i)%mod;
            for(j=dp[0][0]=1;j<=n;j++){
                dp[j][0]=dp[j-1][0]*((a[j]&(1<<i)-1)+1)%mod;
                dp[j][1]=dp[j-1][1]*((a[j]&(1<<i)-1)+1)%mod;
                dp[j][2]=dp[j-1][2]*((a[j]&(1<<i)-1)+1)%mod;
                if(a[j]>>i&1){
                    (dp[j][2]+=dp[j-1][1]*p)%=mod;
                    (dp[j][1]+=dp[j-1][0]+dp[j-1][2]*p)%=mod;
                }
            }
            (c+=dp[n][2])%=mod;
        }
        for(i=1;i<=n;i++)c=c*ksm(a[i]+1,mod-2)%mod;
        cout<<c<<'\n';
    }
}

::::