当前位置: 代码迷 >> 综合 >> 期望——Vasya and Magic Matrix
  详细解决方案

期望——Vasya and Magic Matrix

热度:57   发布时间:2024-02-11 05:37:51.0

题解:

对于当前点来说,权值比他小的每一点都是等概率的。所以对当前点的权值进行从小到大排序,然后概率dp,状态转移的方程很好就求出来了。

#include <bits/stdc++.h>
//#define int long long
using namespace std;
using namespace std;
const int N=10000010;
int n, m, sumx, sumy, sump, dp[N], sumdp, x, y, tot;
struct point { int x, y, val; } p[N];
const int mod = 998244353;
void up(int &x, int y) { if ((x += y) >= mod) x -= mod; }
using LL = long long;
int pow(int x, int y) {int ans = 1;for (; y; y >>= 1, x = static_cast<LL> (x) * x % mod)if (y & 1) ans = static_cast<LL> (ans) * x % mod;return ans;
}
signed main() {std::scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) std::scanf("%d", &p[++tot].val), p[tot].x = i, p[tot].y = j;std::scanf("%d%d", &x, &y);std::sort(p + 1, p + tot + 1, [] (point A, point B) { return A.val < B.val; });for (int i = 1, l = 1; i <= tot; i++) {dp[i] = 0;if (p[i].val != p[l].val)for (; l < i; l++) up(sumx, p[l].x), up(sumy, p[l].y), up(sump, p[l].x * p[l].x + p[l].y * p[l].y), up(sumdp, dp[l]);int n = l - 1;up(dp[i], static_cast<LL> (n) * (p[i].x * p[i].x + p[i].y * p[i].y) % mod);up(dp[i], mod - 2 * (static_cast<LL> (p[i].x) * sumx % mod + static_cast<LL> (p[i].y) * sumy % mod) % mod);up(dp[i], (sump + sumdp) % mod);dp[i] = static_cast<LL> (dp[i]) * pow(n, mod - 2) % mod;if (p[i].x == x && p[i].y == y) {std::printf("%d\n", dp[i]);return 0;}}return 0;
}
  相关解决方案