自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:14:23，当前版本为作者最后更新于2025-04-24 18:37:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}