抚州城乡建设厅网站,厦门企业宣传片制作,intitle 无线网站制作,企业网站建设实训体会传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
将矩阵中的数放到数组里排序#xff0c;就是一个比较明显的期望dpdpdp了。 定义f[i]f[i]f[i]表示从第iii个出发的期望得分#xff0c;所以转移方程也比较好写了#xff1a;f[i]∑(f[j](…传送门
文章目录题意思路题意 思路
将矩阵中的数放到数组里排序就是一个比较明显的期望dpdpdp了。 定义f[i]f[i]f[i]表示从第iii个出发的期望得分所以转移方程也比较好写了f[i]∑(f[j](x[i]−x[j])2(y[i]−y[j])2)cntf[i]\frac{\sum(f[j](x[i]-x[j])^2(y[i]-y[j])^2)}{cnt}f[i]cnt∑(f[j](x[i]−x[j])2(y[i]−y[j])2) 但是这样有个问题如果直接转移的话那就是O(n2m2)O(n^2m^2)O(n2m2)的了看到平方这些东西我们会本能的拆开所以我们考虑化简式子来进行O(1)O(1)O(1)转移。 对于分母∑f[j](x[i]2y[i]2)∗cnt∑(x[j]2y[j]2)−2∗x[i]∗∑x[j]−2∗y[i]∗∑y[j]\sum f[j](x[i]^2y[i]^2)*cnt\sum(x[j]^2y[j]^2)-2*x[i]*\sum x[j]-2*y[i]* \sum y[j]∑f[j](x[i]2y[i]2)∗cnt∑(x[j]2y[j]2)−2∗x[i]∗∑x[j]−2∗y[i]∗∑y[j] 我们发现我们只需要维护∑f[j],∑(x[j]2y[j]2),∑x[j],∑y[j]\sum f[j],\sum(x[j]^2y[j]^2),\sum x[j],\sum y[j]∑f[j],∑(x[j]2y[j]2),∑x[j],∑y[j]即可实现O(1)O(1)O(1)转移了。 实现的时候需要等相同的值都算完了才能加上他们的贡献且由于每个点的x,yx,yx,y都不同需要单独计算一开始以为一样就在代码的797979行鬼使神差的写成了f[i]f[i−1]f[i]f[i-1]f[i]f[i−1]真是老笨蛋啦。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod998244353,INF0x3f3f3f3f;
const double eps1e-6;int n,m,tot;
LL f[N],pref,prex,prey,prex2,prey2,pre;
struct Node
{LL x,y,val;bool operator (const Node w) const{return valw.val;}
}a[N];LL qmi(LL a,LL b)
{LL ans1;while(b){if(b1) ansans*a%mod;aa*a%mod;b1;}return ans%mod;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;in;i) for(int j1;jm;j) { LL x; scanf(%lld,x); a[tot]{i,j,x}; }sort(a1,a1tot);int cnt0; a[0].val-1;for(int i2;itot;i){if(a[i].val!a[i-1].val){int posi-1,vala[i-1].val;while(pos1a[pos].valval) (prexa[pos].x)%mod,(preya[pos].y)%mod,(prex2a[pos].x*a[pos].x)%mod,(prey2a[pos].y*a[pos].y)%mod,(pref[pos])%mod,pos--,cnt;f[i]((pre(a[i].x*a[i].xa[i].y*a[i].y)*cntprex2prey2-2*a[i].x*prex-2*a[i].y*prey)%modmod)%mod*qmi(cnt,mod-2)%mod;}else f[i]((pre(a[i].x*a[i].xa[i].y*a[i].y)*cntprex2prey2-2*a[i].x*prex-2*a[i].y*prey)%modmod)%mod*qmi(cnt,mod-2)%mod;}LL ans-1;int sx,sy; cinsxsy;for(int i1;itot;i) if(a[i].xsxa[i].ysy) { ansf[i]; break; }coutans%modendl;return 0;
}
/*
1 4
1 1 2 1
1 3
*/
