NOIP2023模拟10联测31 迷路

题目大意

你在野外迷路了, 你手里只有一张你当前所在的区域的地图。地图将整个区域表示为$n\times m$的网格，你就在其中的某一个格子里。每个格子里要么有树，要么就什么都没有。地图显示了每个格子中是有树还是空的。当然，地图只记载了这个区域的情况，你可以认为地图外的地方是一片无限延伸的空地（没有树）。你现在可以做的就是探索这个区域，以找到你的出发点（保证你的出发点一开始一定在地图内）。你会按照螺旋形的顺序探索这个区域： 先往下一格，然后往右一格，接着往上一格，接着往上一格，接着往左一格，接着往左一格，接着往下一格… …下面演示了这种顺序，数字代表你探索的顺序。在一个网格中，你能知道的唯一信息就是这里是否有一棵树。地图上的区域中有$k$个格子是有树的。

$$\begin{gathered} 2019181716 \\ 2165415 \\ 2270314 \\ 2381213 \\ 249101112 \end{gathered}$$

现在你遇到了一个商人，他会告诉你地图上的$r$个坐标，其中一个坐标就是你的起点。你想计算出如果你从所有$n\times m$个格子中等概率地选择$r$个格子，你为了区分起始点所需走的步数的期望值。

“你为了区分起始点所需走的步数”指的是，对于给定的$r$个可能的起始点中的任意一个起点，你都要通过在这几步内得到的信息判断出你在这$r$个点中应该是从这个点开始的，所需走的最少步数。步数是你探索的网格数（因此起始网格被视为一步）。

输入有四个数$n,m,k,r$，然后有$k$行，每行两个数$x,y$，表示一个有树的格子的坐标。保证坐标两两不同。

输出期望值模$998244353$后的值。

$1\le n,m\le 300,1\le k,r\le \min (n\times m,300)$

题解

我们考虑对于每一步，维护每个起点收到的信息的等价类，那么我们能区分这$r$个点当且仅当这$r$个点所在不同的等价类互不相同，这个的概率可以用$DP$算出。时间复杂度为$O(n^2{m}^{2}r)$。

我们考虑维护等价类，一共有$nm$步，维护每一步的时间复杂度为$O(nm)$，所以总时间复杂度是$O(n^2{m}^2)$的。但是我们发现树的数量比较少，所以可以用每棵树来更新每个点。于是，对于每一步，将当前这一步有树的起点从其所在的等价类中单独剥离出来，这样总时间复杂度就变为$O(nmk)$的了。

考虑朴素$DP$：设$f_{i,j}$表示在前$i$个等价类中选择了$j$个数，使得它们在不同等价类中的方案数。这样每次计算的时间复杂度为$O(nmr)$，总时间复杂度为$O(n^2{m}^{2}r)$。考虑优化，设当前等价类的大小分别为$a_1,a_2,\dots ,a_p$，那么方案数为$[x^r]\prod _{i=1}^p(1+a_{i}x)$。我们可以实时维护后面的多项式，因为等价类最多只会有$nm$次分裂，每次将一个大小为$a$的等价类分为$b$和$c$时，对这个多项式进行的操作就是除以$(1+ax)$然后乘上$(1+bx)(1+cx)$，这些都可以在$O(r)$的时间复杂度下完成，所以总时间复杂度为$O(nmr)$。

总时间复杂度为$O(nmk+nmr)$。

可以参考代码帮助理解。

code

#include<bits/stdc++.h>
using namespace std;
const int N=300;
const long long mod=998244353;
int n,m,k,R,mx=0,tot=1,x[N+5],y[N+5],z[2*N+5][2*N+5];
long long lst,ans,jc[N*N+5],ny[N*N+5],a[N*N+5];
vector<int>w[N*N+5],v[N*N+5];
set<int>s;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void init(){jc[0]=1;for(int i=1;i<=N*N;i++) jc[i]=jc[i-1]*i%mod;ny[N*N]=mi(jc[N*N],mod-2);for(int i=N*N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
void del(int v){for(int i=1;i<=R;i++) a[i]=(a[i]-a[i-1]*v%mod+mod)%mod;
}
void add(int v){for(int i=R;i>=1;i--) a[i]=(a[i]+a[i-1]*v)%mod;
}
int main()
{
//	freopen("lost.in","r",stdin);
//	freopen("lost.out","w",stdout);init();scanf("%d%d%d%d",&n,&m,&k,&R);if(R==1){printf("0");return 0;}for(int i=1;i<=k;i++){scanf("%d%d",&x[i],&y[i]);}z[300][300]=1;for(int i=1;i<=300;i++){for(int j=-i+1;j<=i;j++) z[300+i][300+j]=++tot;for(int j=i-1;j>=-i;j--) z[300+j][300+i]=++tot;for(int j=i-1;j>=-i;j--) z[300-i][300+j]=++tot;for(int j=-i+1;j<=i;j++) z[300+j][300-i]=++tot;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int id=(i-1)*m+j;for(int p=1;p<=k;p++){w[id].push_back(z[300+x[p]-i][300+y[p]-j]);}sort(w[id].begin(),w[id].end());}}sort(w+1,w+n*m+1);for(int i=2;i<=n*m;i++){int p;for(int j=0;j<k;j++){if(w[i-1][j]!=w[i][j]){p=w[i-1][j]-1;mx=max(mx,p);break;}}v[p].push_back(i);}a[0]=1;add(n*m);s.insert(1);s.insert(n*m+1);for(int i=0;i<=mx;i++){for(int j=0;j<v[i].size();j++){int p=v[i][j];set<int>::iterator it=s.upper_bound(p);int l=*(prev(it)),r=(*it);del(r-l);add(p-l);add(r-p);s.insert(p);}ans=(ans+(a[R]-lst+mod)%mod*(i+1)%mod)%mod;lst=a[R];}ans=ans*mi(C(n*m,R),mod-2)%mod;printf("%lld",ans);return 0;
}