E. Vasya and Magic Matrix

http://codeforces.com/contest/1042/problem/E

题意:

  一个n*m的矩阵,每个位置有一个元素,给定一个起点,每次随机往一个小于这个点位置走,走过去的值为欧几里得距离的平方,求期望的值。

分析:

  逆推期望。

  将所有值取出,按元素大小排序,然后最小的就是0,往所有大于它的转移即可,复杂度n^2,见下方考试代码。

  考虑每个点,从所有小于它的元素转移。排序后,维护前缀和,可以做到O(1)转移。

  $f[i] = \sum\limits_{j=1,val[j]<val[i]}f[j] + (x_j - x_i)^2 + (y_j - y_i) ^ 2$

  $f[i] =\sum\limits_{j=1,val[j]<val[i]} f[j] + x_j^2 - 2x_jx_i + x_i^2 + y_j^2 - 2y_jy_i + y_i ^ 2$

代码:

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const LL mod = ;
const int N = ; struct Node {
int x, y, val;
bool zh;
bool operator < (const Node &A) const {
return val < A.val;
}
}A[N];
LL f[N], cnt[N], sumx[N], sumy[N], sumx2[N], sumy2[N]; LL ksm(LL a,LL b) {
LL ans = ;
while (b) {
if (b & ) ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return ans;
} inline void add(LL &x,LL y) { (x += y) >= mod ? (x -= mod) : x; }
inline void sub(LL &x,LL y) { (x -= y) < ? (x += mod) : x; } void solve2(int n) { A[].val = -;
for (int i=; i<=n; ++i) {
if (A[i].val == A[i - ].val) cnt[i] = cnt[i - ];
else cnt[i] = i - ;
sumx[i] = (sumx[i - ] + A[i].x) % mod;
sumy[i] = (sumy[i - ] + A[i].y) % mod;
sumx2[i] = (sumx2[i - ] + 1ll * A[i].x * A[i].x % mod) % mod;
sumy2[i] = (sumy2[i - ] + 1ll * A[i].y * A[i].y % mod) % mod;
} LL sum = , tmp = ;
for (int i=; i<=n; ++i) {
LL x2 = sumx2[cnt[i]];
LL y2 = sumy2[cnt[i]];
LL z1 = 1ll * sumx[cnt[i]] * % mod * A[i].x % mod;
LL z2 = 1ll * sumy[cnt[i]] * % mod * A[i].y % mod;
LL h1 = 1ll * cnt[i] * A[i].x % mod * A[i].x % mod;
LL h2 = 1ll * cnt[i] * A[i].y % mod * A[i].y % mod; add(f[i], x2); add(f[i], y2);
sub(f[i], z1); sub(f[i], z2);
add(f[i], h1); add(f[i], h2);
add(f[i], sum); f[i] = 1ll * f[i] * ksm(cnt[i], mod - ) % mod;
if (A[i].zh) {
cout << f[i]; return ;
}
add(tmp, f[i]); // 只有小于的时候才转移!!!
if (A[i].val < A[i + ].val) add(sum, tmp), tmp = ;
} } int main() {
int n = read(), m = read(), tot = ;
for (int i=; i<=n; ++i)
for (int j=; j<=m; ++j)
A[++tot].x = i, A[tot].y = j, A[tot].val = read(), A[tot].zh = false; int x = read(), y = read(), z = (x - ) * m + y;
A[z].zh = true; sort(A + , A + tot + ); solve2(tot);
return ;
}

比赛时代码,记录调试历程。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const LL mod = ;
const int N = ; struct Node {
int x, y, val;
bool zh;
bool operator < (const Node &A) const {
return val < A.val;
}
}A[N]; LL inv[N], deg[N], f[N];
//double dp[N]; LL ksm(LL a,LL b) {
LL ans = ;
while (b) {
if (b & ) ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return ans;
} LL Calc(int i,int j) {
return ((A[i].x - A[j].x) * (A[i].x - A[j].x) % mod + (A[i].y - A[j].y) * (A[i].y - A[j].y) % mod) % mod;
} void solve1(int n) {
for (int i=; i<=n; ++i) {
// cout << A[i].val << ": ";
if (deg[i]) {
// dp[i] = dp[i] / (double)(deg[i]);
f[i] = 1ll * ksm(deg[i], mod - ) * f[i] % mod;
}
if (A[i].zh) {
cout << f[i]; return ;
}
for (int j=i+; j<=n; ++j)
if (A[j].val > A[i].val) {
// dp[j] = dp[j] + dp[i] + Calc(i, j);
// cout << A[j].val << " " << Calc(i, j) <<"--";
f[j] = (f[j] + f[i] + Calc(i, j)) % mod;
deg[j] ++;
}
// puts("");
}
} int cnt[N], sumx[N], sumy[N], sumx2[N], sumy2[N]; inline void add(LL &x,LL y) { (x += y) >= mod ? (x -= mod) : x; }
inline void sub(LL &x,LL y) { (x -= y) < ? (x += mod) : x; } void solve2(int n) { A[].val = -;
for (int i=; i<=n; ++i) {
if (A[i].val == A[i - ].val) cnt[i] = cnt[i - ];
else cnt[i] = i - ;
sumx[i] = (sumx[i - ] + A[i].x) % mod;
sumy[i] = (sumy[i - ] + A[i].y) % mod;
sumx2[i] = (sumx2[i - ] + 1ll * A[i].x * A[i].x % mod) % mod;
sumy2[i] = (sumy2[i - ] + 1ll * A[i].y * A[i].y % mod) % mod;
} LL sum = , tmp = ;
for (int i=; i<=n; ++i) {
LL x2 = sumx2[cnt[i]];
LL y2 = sumy2[cnt[i]];
LL z1 = 1ll * sumx[cnt[i]] * % mod * A[i].x % mod;
LL z2 = 1ll * sumy[cnt[i]] * % mod * A[i].y % mod;
LL h1 = 1ll * cnt[i] * A[i].x % mod * A[i].x % mod;
LL h2 = 1ll * cnt[i] * A[i].y % mod * A[i].y % mod; add(f[i], x2); add(f[i], y2);
sub(f[i], z1); sub(f[i], z2);
add(f[i], h1); add(f[i], h2);
add(f[i], sum); f[i] = 1ll * f[i] * ksm(cnt[i], mod - ) % mod;
if (A[i].zh) {
cout << f[i]; return ;
}
add(tmp, f[i]); // 只有小于的时候才转移!!!
if (A[i].val < A[i + ].val) add(sum, tmp), tmp = ;
} } int main() {
int n = read(), m = read(), tot = ;
for (int i=; i<=n; ++i)
for (int j=; j<=m; ++j)
A[++tot].x = i, A[tot].y = j, A[tot].val = read(), A[tot].zh = false; int x = read(), y = read(), z = (x - ) * m + y;
A[z].zh = true; sort(A + , A + tot + ); // if (tot <= 1000) {
// solve1(tot) ;return 0;
// }
solve2(tot);
return ;
}

最新文章

  1. vim配置及快捷键
  2. 修改Hosts为何不生效,是DNS缓存?
  3. NOI2009 诗人小G
  4. js获取select改变事件
  5. WIN7启动WIFI
  6. file not found while xcode archive
  7. javaSE第十九天
  8. 《c程序设计语言》读书笔记--首次输入不能是空符;最多10个字符
  9. ScrollView嵌套ListView的滑动冲突问题,是看大神的方法的,作为学习以后用的到
  10. 关于fft的一点总结
  11. jQuery图片滑动
  12. ASP.NET 获取IP信息等探针
  13. 浅谈js闭包
  14. java ArrayList的序列化分析
  15. Java中函数的递归调用
  16. MT【247】恒成立画图像
  17. 微软BI 之SSIS 系列 - 数据仓库中实现 Slowly Changing Dimension 缓慢渐变维度的三种方式
  18. java中那些类是线程安全的?
  19. 使用json-org包实现POJO和json的转换
  20. js九九乘法表的应用

热门文章

  1. 自动生成气泡对话框的jQuery插件CreateBubble.js
  2. 牛客网多校训练第三场 A - PACM Team(01背包变形 + 记录方案)
  3. MySQL数据库------常用函数
  4. 十三、IntelliJ IDEA 中的版本控制介绍(下)
  5. PAT——1055. 集体照 (比较comparable和comparator的区别)
  6. CSS Variables
  7. Undefined symbols for architecture arm64: &quot;_OBJC_CLASS_$XXX&quot;, referenced from: objc-class-ref in XXX
  8. 【Django笔记四】Django2.0中的表单
  9. 【reidis中ruby模块版本老旧利用rvm来更新】
  10. 使用EF Core的CodeFirt 出现的问题The specified framework version &#39;2.1&#39; could not be parsed