自动搬运

查看原文

来自洛谷，原作者为

	Alarm5854 Stop Smoking!

搬运于2025-08-24 22:40:22，当前版本为作者最后更新于2021-09-03 21:51:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

来自本题出题人官方题解，过了近两个月才想起来发，写得很丑，赛时果然被爆标了。

题意

一开始有一个带 $n$ 个点的环，从 $1$ 到 $n$ 顺时针排列。

设上一个点返回的状态为 $x$，则：

• 若 $x=1$，则这个环上第 $i$ 个点有 $\dfrac{a_i}{1000}$ 的概率返回 $1$ 且删除这个点，有 $\dfrac{b_i}{1000}$ 的概率返回 $1$ 但保留这个点，有 $\dfrac{1000-a_i-b_i}{1000}$ 的概率返回 $2$ 且保留这个点。
• 若 $x=2$，则这个环上第 $i$ 个点有 $\dfrac{a_i+b_i}{1000}$ 的概率返回 $1$ 且删除这个点，有 $\dfrac{1000-a_i-b_i}{1000}$ 的概率返回 $2$ 且保留这个点。

初始 $x=1$，从 $1$ 号点开始进行上述操作，操作完后找到沿顺时针方向下一个点，这个点成为下一个操作的点。

求只剩一个点的期望操作次数，若期望次数为无穷大，输出 $-1$，否则输出这个概率对 $10^6+33$ 取模的值，可以证明答案为有理数。

前置知识

期望，状压，高斯消元。

子任务 $1$

很明显，一开始就只有一个点，期望改变状态次数为 $0$。

期望得分 $2$ 分。

子任务 $2$

这时每个点肯定会返回 $2$ 且被保留，因此当 $n>1$ 时期望次数为无穷大，$n=1$ 时期望次数为 $0$。

期望得分 $4$ 分（这里的期望得分均为结合前面的子任务的得分）。

子任务 $3$

这时每个点肯定会返回 $1$ 且被删除，因此到 $n$ 号点的时候就只剩一个点了，答案即为 $n-1$。

期望得分 $8$ 分。

子任务 $4$

这时每个点肯定会返回 $1$ 且被保留，因此情况同子任务 $2$。

期望得分 $12$ 分。

子任务 $5$

这时 $1$ 号点一直返回 $2$，设这是第 $i$ 圈，则 $i+1$ 号点会返回 $1$ 并被删除，$i+2\sim n$ 会返回 $1$ 并被保留。第 $i(i<n)$ 圈的操作次数为 $n-i+1$，第 $n$ 圈不用操作，故答案为 $\dfrac{n(n+1)}{2}-1$。

期望得分 $18$ 分。

子任务 $6$

这时每个点都本质相同，且没有任何点返回 $2$，设 $f(n)$ 为剩 $n$ 个点时的期望次数，则

$$f(1)=0,f(n)=\dfrac{1}{2}(f(n-1)+f(n))+1$$

得出

$$f(n)=2(n-1)$$

期望得分 $24$ 分。

子任务 $7$

这时每个点仍然本质相同，设 $f(n)$ 为剩 $n$ 个点，且 $x=1$ 的期望次数，$g(n)$ 为剩 $n$ 个点，且 $x=2$ 的期望次数。

那么有

$$f(1)=0,f(n)=\dfrac{1}{2}(f(n)+g(n))+1$$ $$g(n)=\dfrac{1}{2}(f(n-1)+g(n))+1$$

得出

$$f(n)=4(n-1)$$

期望得分 $30$ 分。

子任务 $8$

其实就是子任务 $6,7$ 的拓展版本，按照前面所说，则

$$f(1)=0,f(n)=\dfrac{a_i}{1000}f(n-1)+\dfrac{b_i}{1000}f(n)+\dfrac{1000-a_i-b_i}{1000}g(n)+1 $$$$g(n)=\dfrac{a_i+b_i}{1000}f(n-1)+\dfrac{1000-a_i-b_i}{1000}g(n)+1 $$

解得

$$f(n)=\dfrac{1000\times (n-1)}{(a_i+b_i)\times(1-b_i)} $$

期望得分 $49$ 分。

子任务 $9$

进入正题，由于 $n\le11$，于是可以想到状压。

从这里开始 $a_i$ 表示前面的 $a_{i+1}$。

设 $f(S,i)$ 表示剩余的点的状态为 $S$，现在在这个状态中第 $i$ 个为 $1$ 的地方 (0下标) ，上一个点的返回值为 $1$ 的期望局数，$g(S,i)$ 和 $f(S,i)$ 的区别在于变成上一个点返回值为 $2$ 的期望局数，则有：

$$f(2^k,x)=0(k\in \mathbb{N},x\le k)$$

这就是题目中的定义，$f(S,i)$ 的转移为：

$$\begin{aligned} f(S,i)&=\dfrac{a_{S_i}}{1000}f(S\oplus 2^{S_i},i\bmod (|S|-1))\\&+\dfrac{b_{S_i}}{1000}f(S,(i+1)\bmod |S|)\\&+\dfrac{1000-a_{S_i}-b_{S_i}}{1000}g(S,(i+1)\bmod |S|) \end{aligned} $$$$\begin{aligned} g(S,i)&=\dfrac{a_{S_i}+b_{S_i}}{1000}f(S\oplus 2^{S_i},i\bmod (|S|-1))\\&+\dfrac{1000-a_{S_i}-b_{S_i}}{1000}g(S,(i+1)\bmod |S|) \end{aligned} $$

这样，可以考虑对于每一个 $S\in[1,2^n),S\neq 2^k,k\in\mathbb{N}$，都列出这样的 $2\times |S|$ 元的线性方程，可以用高斯消元解决。

至于怎么高斯消元，需要对上述的式子进行变形：

$$\begin{aligned} f(S,i)&-\dfrac{b_{S_i}}{1000}f(S,(i+1)\bmod |S|)-\dfrac{1-a_{S_i}-b_{S_i}}{1000}g(S,(i+1)\bmod |S|)\\&=\dfrac{a_{S_i}}{1000}f(S\oplus 2^{S_i},i\bmod (|S|-1)) \end{aligned} $$$$\begin{aligned} g(S,i)&-\dfrac{1000-a_{S_i}-b_{S_i}}{1000}g(S,(i+1)\bmod |S|)\\&=\dfrac{a_{S_i}+b_{S_i}}{1000}g(S\oplus 2^{S_i},i\bmod (|S|-1)) \end{aligned} $$

这样就能够把高斯消元矩阵构造出来了，大小为 $2n\times(2n+1)$。

尤其需要注意的是如果出现了除以 $0$ 的情况，一定要把这个答案弄成一个不在 $[0,p)$ 范围内的数并进行特判，否则会出问题。

朴素的高斯消元复杂度为 $O(n^3)$，快速幂的复杂度为 $O(\log p)$，其中 $\log p$ 与 $n$ 同阶，故时间复杂度为 $O(2^n\times n^4)$（实际上是 $O(2^n\times n^3\times \log p)$）。

期望得分 $75$ 分。

子任务 $10$

由于 $p=10^6+33$，所以考虑预处理逆元，这样可以将复杂度降至 $O(2^n\times n^3)$。

期望得分 $83$ 分。

子任务 $11$

发现这个矩阵是个稀疏矩阵，每列非 $0$ 的元素数量很少，对于一列为 $0$ 的，就不需要进行减法，因为这是无效的，这样复杂度可以降至 $O(2^n\times n^2)$。

期望得分 $100$ 分。

标程

//去掉注释后长度：2053字节
#include<ctime>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll p=1e6+33;
const ll N=18;
int read(){
	char c;
	int x=0,f=1;
	while(!isdigit(c=getchar()))
		f-=2*(c=='-');
	while(isdigit(c)){
		x=x*10+f*(c-48);
		c=getchar();
	}
	return x;
}
ll n,t,k,a[21],b[21],f[1<<N][21];
ll l[1<<N],g[1<<N],c[37][37],s[37];
ll inv[p];
void gauss(ll n){
	for(ll i=0;i<n;++i){
		ll t=i;
		for(ll j=i;j<n;++j){
			if(c[j][i]){
				t=j;
				break;
			}
		}
		if(!c[t][i])
			continue;
		swap(c[i],c[t]);
		for(ll j=i+1;j<n;++j){
			if(!c[j][i])//优化
				continue;
			ll x=c[j][i]*inv[c[i][i]];
			for(ll k=i;k<=n;++k){
				if(~c[j][k])
					c[j][k]=(c[j][k]-x*c[i][k]%p+p)%p;
			}
		}
	}
	for(ll i=n-1;~i;--i){
		if(!c[i][i]||!~c[i][n])
			s[i]=-1;//这里的-1即为特殊值，需要特判
		else
			s[i]=c[i][n]*inv[c[i][i]]%p;
		if(!i)
			continue;
		for(ll j=i-1;~j;--j){
			if(~c[j][n]&&(~s[i]||!c[j][i]))//仍然需要特判-1
				c[j][n]=(c[j][n]-c[j][i]*s[i]%p+p)%p;
			else
				c[j][n]=-1;
			c[j][i]=0;
		}
	}
}
int main(){
	n=read();
	t=read();
	inv[1]=1;
	k=1<<n;
	for(ll i=2;i<p;++i)
		inv[i]=(p-p/i)*inv[p%i]%p;//线性处理逆元
	for(ll i=0;i<n;++i){
		a[i]=read()*inv[1000]%p;//提前进行转化
		b[i]=read()*inv[1000]%p;
	}
	for(ll i=1;i<k;++i)
		l[i]=l[i^(i&-i)]+1;
	for(ll i=0;i<n;++i)
		g[1<<i]=i;
	for(ll i=1;i<k;++i){
		if(l[i]==1)
			continue;
		memset(c,0,sizeof(c));//初始清空矩阵
		for(ll j=0,t=i;t;t^=t&-t,++j){
			ll x=g[t&-t];
			c[j*2][j*2]=1;
			c[j*2+1][j*2+1]=1;
			c[j*2][(j*2+2)%(l[i]*2)]=(p-b[x]%p)%p;
			c[j*2][(j*2+3)%(l[i]*2)]=(a[x]+b[x]-1+p)%p;//由于一开始进行了处理，所以就不再是a[x]+b[x]-1000了
			c[j*2+1][(j*2+3)%(l[i]*2)]=(a[x]+b[x]-1+p)%p;
			if(~f[i^(1<<x)][j%(l[i]-1)]||!a[x])
				c[j*2][l[i]*2]=(a[x]*f[i^(1<<x)][j%(l[i]-1)]+1)%p;
			else
				c[j*2][l[i]*2]=-1;
			if(~f[i^(1<<x)][j%(l[i]-1)]||!(a[x]+b[x]))
				c[j*2+1][l[i]*2]=((a[x]+b[x])*f[i^(1<<x)][j%(l[i]-1)]+1)%p;
			else
				c[j*2+1][l[i]*2]=-1;
        //c[j*2]为f所对应的位置，c[j*2+1]为g所对应的位置
		}
		gauss(l[i]*2);
		for(int j=0;j<l[i];++j)
			f[i][j]=s[j*2];
	}
	printf("%lld\n",f[k-1][0]);
	return 0;
}