NOIP2023模拟10联测31 迷路

联测31 迷路"/>

NOIP2023模拟10联测31 迷路

题目大意

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

20 19 18 17 16 21 6 5 4 15 22 7 0 3 14 23 8 1 2 13 24 9 10 11 12 20 \ 19 \ 18 \ 17 \ 16 \\ 21 \ \ 6 \ \ \ 5 \ \ \ 4 \ \ 15 \\ 22 \ \ 7 \ \ \ 0 \ \ \ 3 \ \ 14 \\ 23 \ \ 8 \ \ \ 1 \ \ \ 2 \ \ 13 \\ 24 \ \ 9 \ \ 10 \ 11 \ 12 20 19 18 17 1621  6   5   4  1522  7   0   3  1423  8   1   2  1324  9  10 11 12

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

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

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

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

1 ≤ n , m ≤ 300 , 1 ≤ k , r ≤ min ⁡ ( n × m , 300 ) 1\leq n,m\leq 300,1\leq k,r\leq \min(n\times m,300) 1≤n,m≤300,1≤k,r≤min(n×m,300)

题解

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

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

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

总时间复杂度为 O ( n m k + n m r ) O(nmk+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;
}