手机怎样建立自己网站,wordpress百度和分类,完全不收费的聊天软件,网站服务器容器题目大意
你在野外迷路了, 你手里只有一张你当前所在的区域的地图。地图将整个区域表示为 n m n\times m nm的网格#xff0c;你就在其中的某一个格子里。每个格子里要么有树#xff0c;要么就什么都没有。地图显示了每个格子中是有树还是空的。当然#xff0c;地图只记载…题目大意
你在野外迷路了, 你手里只有一张你当前所在的区域的地图。地图将整个区域表示为 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_{i1}^p(1a_ix) [xr]i1∏p(1aix)。我们可以实时维护后面的多项式因为等价类最多只会有 n m nm nm次分裂每次将一个大小为 a a a的等价类分为 b b b和 c c c时对这个多项式进行的操作就是除以 ( 1 a x ) (1ax) (1ax)然后乘上 ( 1 b x ) ( 1 c x ) (1bx)(1cx) (1bx)(1cx)这些都可以在 O ( r ) O(r) O(r)的时间复杂度下完成所以总时间复杂度为 O ( n m r ) O(nmr) O(nmr)。
总时间复杂度为 O ( n m k n m r ) O(nmknmr) O(nmknmr)。
可以参考代码帮助理解。
code
#includebits/stdc.h
using namespace std;
const int N300;
const long long mod998244353;
int n,m,k,R,mx0,tot1,x[N5],y[N5],z[2*N5][2*N5];
long long lst,ans,jc[N*N5],ny[N*N5],a[N*N5];
vectorintw[N*N5],v[N*N5];
setints;
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void init(){jc[0]1;for(int i1;iN*N;i) jc[i]jc[i-1]*i%mod;ny[N*N]mi(jc[N*N],mod-2);for(int iN*N-1;i0;i--) ny[i]ny[i1]*(i1)%mod;
}
long long C(int x,int y){return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
void del(int v){for(int i1;iR;i) a[i](a[i]-a[i-1]*v%modmod)%mod;
}
void add(int v){for(int iR;i1;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(R1){printf(0);return 0;}for(int i1;ik;i){scanf(%d%d,x[i],y[i]);}z[300][300]1;for(int i1;i300;i){for(int j-i1;ji;j) z[300i][300j]tot;for(int ji-1;j-i;j--) z[300j][300i]tot;for(int ji-1;j-i;j--) z[300-i][300j]tot;for(int j-i1;ji;j) z[300j][300-i]tot;}for(int i1;in;i){for(int j1;jm;j){int id(i-1)*mj;for(int p1;pk;p){w[id].push_back(z[300x[p]-i][300y[p]-j]);}sort(w[id].begin(),w[id].end());}}sort(w1,wn*m1);for(int i2;in*m;i){int p;for(int j0;jk;j){if(w[i-1][j]!w[i][j]){pw[i-1][j]-1;mxmax(mx,p);break;}}v[p].push_back(i);}a[0]1;add(n*m);s.insert(1);s.insert(n*m1);for(int i0;imx;i){for(int j0;jv[i].size();j){int pv[i][j];setint::iterator its.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]-lstmod)%mod*(i1)%mod)%mod;lsta[R];}ansans*mi(C(n*m,R),mod-2)%mod;printf(%lld,ans);return 0;
}
