題目大意

你在野外迷路了, 你手里只有一張你當(dāng)前所在的區(qū)域的地圖。地圖將整個區(qū)域表示為$n\times m$的網(wǎng)格，你就在其中的某一個格子里。每個格子里要么有樹，要么就什么都沒有。地圖顯示了每個格子中是有樹還是空的。當(dāng)然，地圖只記載了這個區(qū)域的情況，你可以認為地圖外的地方是一片無限延伸的空地（沒有樹）。你現(xiàn)在可以做的就是探索這個區(qū)域，以找到你的出發(fā)點（保證你的出發(fā)點一開始一定在地圖內(nèi)）。你會按照螺旋形的順序探索這個區(qū)域： 先往下一格，然后往右一格，接著往上一格，接著往上一格，接著往左一格，接著往左一格，接著往下一格… …下面演示了這種順序，數(shù)字代表你探索的順序。在一個網(wǎng)格中，你能知道的唯一信息就是這里是否有一棵樹。地圖上的區(qū)域中有$k$個格子是有樹的。

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

現(xiàn)在你遇到了一個商人，他會告訴你地圖上的$r$個坐標(biāo)，其中一個坐標(biāo)就是你的起點。你想計算出如果你從所有$n\times m$個格子中等概率地選擇$r$個格子，你為了區(qū)分起始點所需走的步數(shù)的期望值。

“你為了區(qū)分起始點所需走的步數(shù)”指的是，對于給定的$r$個可能的起始點中的任意一個起點，你都要通過在這幾步內(nèi)得到的信息判斷出你在這$r$個點中應(yīng)該是從這個點開始的，所需走的最少步數(shù)。步數(shù)是你探索的網(wǎng)格數(shù)（因此起始網(wǎng)格被視為一步）。

輸入有四個數(shù)$n,m,k,r$，然后有$k$行，每行兩個數(shù)$x,y$，表示一個有樹的格子的坐標(biāo)。保證坐標(biāo)兩兩不同。

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

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

題解

我們考慮對于每一步，維護每個起點收到的信息的等價類，那么我們能區(qū)分這$r$個點當(dāng)且僅當(dāng)這$r$個點所在不同的等價類互不相同，這個的概率可以用$DP$算出。時間復(fù)雜度為$O(n^2{m}^{2}r)$。

我們考慮維護等價類，一共有$nm$步，維護每一步的時間復(fù)雜度為$O(nm)$，所以總時間復(fù)雜度是$O(n^2{m}^2)$的。但是我們發(fā)現(xiàn)樹的數(shù)量比較少，所以可以用每棵樹來更新每個點。于是，對于每一步，將當(dāng)前這一步有樹的起點從其所在的等價類中單獨剝離出來，這樣總時間復(fù)雜度就變?yōu)?span id="vxwlu0yf4" class="katex--inline">$O(nmk)$的了。

考慮樸素$DP$：設(shè)$f_{i,j}$表示在前$i$個等價類中選擇了$j$個數(shù)，使得它們在不同等價類中的方案數(shù)。這樣每次計算的時間復(fù)雜度為$O(nmr)$，總時間復(fù)雜度為$O(n^2{m}^{2}r)$?？紤]優(yōu)化，設(shè)當(dāng)前等價類的大小分別為$a_1,a_2,\dots ,a_p$，那么方案數(shù)為$[x^r]\prod _{i=1}^p(1+a_{i}x)$。我們可以實時維護后面的多項式，因為等價類最多只會有$nm$次分裂，每次將一個大小為$a$的等價類分為$b$和$c$時，對這個多項式進行的操作就是除以$(1+ax)$然后乘上$(1+bx)(1+cx)$，這些都可以在$O(r)$的時間復(fù)雜度下完成，所以總時間復(fù)雜度為$O(nmr)$。

總時間復(fù)雜度為$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;
}