题解 CF24D 【Broken robot】

双倍经验 [luogu 治疗之雨](https://www.luogu.org/problemnew/show/P4457) 两题考虑的思路比较类似，操作基本相同。。。就是一个取模一个精度 我们先排除一种特殊情况： m=1 的情况 这个时候我们发现只需要输出 2*(n-1) 就好了，至于具体证明比较显然，留给读者自推吧。。。 我们先考虑根据题意列出 期望的转移式： $$f[i,j]=\begin{cases} {1\over4 } (f[i,j]+f[i,j-1]+f[i,j+1]+f[i+1][j]) +1 && 1< j < m \cr {1\over3 } (f[i,j]+f[i,j+1]+f[i+1][j]) +1 &&j=1\cr {1\over3 } (f[i,j]+f[i,j-1]+f[i+1][j]) +1 &&j=m\end{cases} $$ （至于 m=1 的情况上面已经讨论过了，就不再列入情况内） 于是乎，我们发现这玩意儿是要移项什么的来解的啊。。。 那么我们就处理一下呗~ 情况一：$1<j<m$ $$ 3\times f[i,j] - f[i,j-1] - f[i,j+1]- f[i+1][j] = 4 $$ 情况二：$j=1$ $$ 2\times f[i,j] - f[i,j+1]- f[i+1][j] = 3 $$ 情况三：$j=m$ $$ 2\times f[i,j] - f[i,j-1] - f[i+1][j] = 3 $$ 辣么我们就可以高斯消元解出这道题了 等等，别忘了复杂度： $O(n^6)$ ！ 10 分！（好吧真相是 CF 里没分，这里是我自己给的标准分） >FAQ: 什么鬼！怎么会 $n^6$的，高斯不是三次的么？ >额，这玩意儿是二维的啊，n m 同阶的情况下三次的里面要多个平方 那么我们怎么优化呢？ 我们考虑到每行只与当前层、下一层有关，那么我们可不可以从下到上依次处理每一行呢？ 当然可以！处理完第 i+1 行之后 $f[i+1,j]$ 就成为了常量，当前行的转移计算只要用到当前行的变量就行了 那么...我们考虑这样的复杂度是 $O(n^4)$ >FAQ: 还是过不了啊，1000 的数据呢 >别着急啊，我们再找找性质 怎么说呢，我们发现每个等式用到的变量少的可怜（woc 我好像提到了什么不得了的名字），如果你吧矩阵画一下就会发现鬼畜的地方了： $$ \begin{bmatrix} 2 & -1 &0&0&0&0&0&0&0&0&0\\ -1 & 3&-1&0&0&0&0&0&0&0&0\\ 0&-1 & 3&-1&0&0&0&0&0&0&0\\ 0&0&-1 & 3&-1&0&0&0&0&0&0\\ 0&0&0&-1 & 3&-1&0&0&0&0&0\\0&0&0&0& -1 & 3&-1&0&0&0&0\\ 0&0&0&0&0&-1 & 3&-1&0&0&0\\ -0&0&0&0&0&0&-1 & 3&-1&0&0\\ 0&0&0&0&0&0&0&-1 & 3&-1&0\\ 0&0&0&0&0&0&0&0&-1 &3&-1\\ 0&0&0&0&0&0&0&0&0&-1&2\end{bmatrix} \quad$$ 什么你问我累不累？ $Ctrl~ C\ \ \ \ \ \ \ Ctrl~ V$ 是挺累的... 就是为了看的清楚点嘛... 发现了吧？这是个稀疏图哈~ 那么我们可以考虑对于 n 行操作每次只操作三个元素： $A[i][i],A[i][i+1],A[i][m+1]$，然后用这三个元素对第 i+1 行操作 当然，如果 i+1 = m 的话就是两个元素了 然后从下向上扫一遍将其消为单位矩阵 这样的话我们每次 Gauss 就是 $O(n)$ 的了，加上我们要操作 n 行，复杂度就达到了令人满意的 $O(n^2)$ ~~当然我是不知道有没有 O(1) 公式大毒瘤的~~ 如果你做过了之前提过的那道治疗之雨的话就可以切掉这道题了（那道可是黑色的...虽说个人感觉这两道题好像也差不多，那这道就应该是黑题 $QVQ$， 恭喜你将要 A 掉两道黑题） ``` //by Judge #include<cstdio> #include<iostream> #define fp(i,a,b) for(int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(int i=(a),I=(b)-1;i>I;--i) #define ll long long using namespace std; const int mod=998244353; const int M=1003; typedef int arr[M]; inline int Mul(int a,int b){return 1ll*a*b%mod;} inline void Add(int& a,int b){a+=a+b>=mod?b-mod:b;} inline int qpow(int x,int p=mod-2){ int s=1; for(;p;p>>=1,x=Mul(x,x)) if(p&1) s=Mul(s,x); return s; } int n,m,x,y; double f[M],A[M][M]; inline void Gauss(int n){ fp(i,1,n){ if(i<n) A[i][i+1]/=A[i][i]; A[i][n+1]/=A[i][i],A[i][i]=1; A[i+1][i+1]-=A[i][i+1]*A[i+1][i]; A[i+1][n+1]-=A[i][n+1]*A[i+1][i],A[i+1][i]=0; } fd(i,n-1,1) A[i][n+1]-=A[i][i+1]*A[i+1][n+1]; } int main(){ cin>>n>>m>>x>>y,n-=x-1,x=1; if(m==1) return !printf("%.10lf\n",(double)2*(n-1)); fp(tim,1,n-1){ A[1][1]=2,A[1][2]=-1,A[1][m+1]=f[1]+3; A[m][m]=2,A[m][m-1]=-1,A[m][m+1]=f[m]+3; fp(i,2,m-1) A[i][i-1]=A[i][i+1]=-1; fp(i,2,m-1) A[i][i]=3,A[i][m+1]=f[i]+4; Gauss(m); fp(i,1,m) f[i]=A[i][m+1]; } return !printf("%.10lf\n",f[y]); } ```