题解：P12292 [蓝桥杯 2024 国 Java A] 斗蛐蛐

· · 题解

Solution

数据很小，直接写 O(n^2 2^n)，也就是对每个蛐蛐作为最终结果。唉这个能做到 O(n2^n) 吗。。。

很容易设出 DP 状态：dp_{S,i} 表示剩下编号是 S 的蛐蛐，且当前决策的是 i 时能产生目标局面的概率。

有两种转移：S 中减去一只蛐蛐，到 T \subset S；i 移动一下。

前者启发我们按照 |S| 转移，后者会带来一个很麻烦的事情——转移的后效性。

即，很有可能一轮所有蛐蛐都没成功，这样 S 不变转移到自己身上去了。

转移式子形如 dp_{S,i} = a_i \times f_{S,i} + (1-a_i) dp_{S,i+1}，其中 f_{S,i} 表示的是打败一直蛐蛐的两种情况的平均值。

唉这样有后效性。似乎直接高斯消元是有能通过的风险的，但是我不这么做。特殊矩阵为什么要高斯消元呢！

如果有一个 a_i = 1，那么显然不存在后效性了，可以直接递推。（似乎题目保证了这种情况不会出现？？）

否则，设 dp_{S,i} = k_i dp_{S,1} + b_i，那么得到 dp_{S,i} = a_i f_{S,i} + (1-a_i) (k_{i+1}dp_{S,1}+b_{i+1})，可以得出新的 k 和 b。

显然不会出现 a 全为 0 的情况，虽然题目并没有保证但是一定是这样的。所以我们从 1 开始往前推，转一圈回来会得到 dp_{S,1} = k dp_{S,1} + b，其中 0 < k < 1。可以把 dp_{S,1} 解出来。

复杂度 O(n^2 2^n)。

注意 |S|=2 和 |S|>2 的转移本质不同（主要在后继状态的设计上），不过一点都不难。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=15+1,MAXM=(1<<15)+10;
int n,MOD,a[MAXN],dp[MAXM][MAXN];
int qpow(int base,int p) {
    int ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;   
    }
    return ans;
}
int f[MAXN],k[MAXN],b[MAXN];
int solve(int s) {
    memset(dp,0,sizeof(dp));
    dp[1<<s-1][s]=1;
    ffor(i,1,(1<<n)-1) {
        if(__builtin_popcount(i)==1) continue ;
        vector<int> cir;
        memset(f,0,sizeof(f)),memset(k,0,sizeof(k)),memset(b,0,sizeof(b));
        ffor(j,1,n) if(i&(1<<j-1)) cir.push_back(j);
        ffor(j,0,cir.size()-1) {
            int id=cir[j];
            if(cir.size()>2) {
                f[id]=(f[id]+dp[i-(1<<cir[(j+cir.size()-1)%cir.size()]-1)][cir[(j+1)%cir.size()]])%MOD;
                f[id]=(f[id]+dp[i-(1<<cir[(j+1)%cir.size()]-1)][cir[(j+2)%cir.size()]])%MOD; 
                f[id]=f[id]*(MOD+1)/2%MOD;
            }
            else f[id]=dp[(1<<id-1)][id];   
        }
        k[cir[0]]=1;
        roff(j,cir.size()-1,0) {
            int id=cir[j],nxt=cir[(j+1)%cir.size()];
            k[id]=(1-a[id])*k[nxt]%MOD,b[id]=(a[id]*f[id]+(1-a[id])*b[nxt])%MOD;
        }
        int dp1=b[cir[0]]*qpow(1-k[cir[0]],MOD-2)%MOD;
        for(auto id:cir) dp[i][id]=(dp1*k[id]+b[id])%MOD;
    }
    return (dp[(1<<n)-1][1]%MOD+MOD)%MOD;
}
signed main() {
    cin>>n>>MOD;
    ffor(i,1,n) cin>>a[i];
    ffor(i,1,n) cout<<solve(i)<<' ';
    return 0;
}