建设网站费用主要包括哪些,sdk直播,wordpress 摄影,比较好的网站建设公司电话SRM614 Div1 Hard
题目描述
Solution
显然有#xff1a; E(x,y)(E(x−1,y)E(x,y−1))/21E(x,y)(E(x-1,y)E(x,y-1))/21 E(x,y)(E(x−1,y)E(x,y−1))/21 直接高斯消元时间复杂度O((nm)3)O((nm)^3)O((nm)3)。
可以发现这种做法十分浪费#xff0c;消元之后会有大量冗余元素 E(x,y)(E(x−1,y)E(x,y−1))/21E(x,y)(E(x-1,y)E(x,y-1))/21 E(x,y)(E(x−1,y)E(x,y−1))/21 直接高斯消元时间复杂度O((nm)3)O((nm)^3)O((nm)3)。
可以发现这种做法十分浪费消元之后会有大量冗余元素即零行我们考虑消去这些不必要状态。
我们发现可以只保留最后一行和最后一列的未知数用上面的式子表示其他没有保留的格子再计算答案即可。
时间复杂度O((nm)3)O((nm)^3)O((nm)3)。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN205;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
class TorusSailing
{lod a[MAXN][MAXN],f[MAXN][MAXN][MAXN];private:bool solve(int n){for (int i0;in;i){int maxji;for (int ji1;jn;j)if (fabs(a[j][i])-fabs(a[maxj][i])eps) maxjj;if (fabs(a[maxj][i])eps) return 0;if (maxj!i)for (int j0;jn;j) swap(a[maxj][j],a[i][j]);for (int ji1;jn;j){double ta[j][i]/a[i][i];for (int ki;kn;k) a[j][k]-t*a[i][k];}}for (int in-1;i0;i--){for (int ji1;jn;j) a[i][n]-a[j][n]*a[i][j];a[i][n]/a[i][i];}return 1;} int upd(int x,int y,int mods){ return xy0?xymods:xy; }public:lod expectedTime(int n,int m,int X,int Y){n--,m--;for (int i0;in;i) f[i][m][i]1;for (int i0;im;i) f[n][i][in]1;for (int i0;in;i)for (int j0;jm;j){if (!i!j) continue;for (int k0;knm1;k)f[i][j][k](f[upd(i,-1,n1)][j][k]f[i][upd(j,-1,m1)][k])*0.5;f[i][j][nm1];
// for (int k0;knm1;k) coutsetw(6)f[i][j][k];
// coutendl;} for (int i0;in;i){for (int j0;jnm1;j) a[i][j]f[i][m][j];a[i][nm1]-a[i][nm1];a[i][i]--;} for (int i0;im;i){for (int j0;jnm1;j) a[in][j]f[n][i][j];a[in][nm1]-a[in][nm1];a[in][in]--;} /*for (int i0;inm;i){for (int j0;jnm1;j) coutsetw(6)a[i][j];coutendl;}*/solve(nm1);lod ansf[X][Y][nm1];for (int i0;inm;i) ansf[X][Y][i]*a[i][nm1];return ans;}
};
/*
TorusSailing solve;
int main()
{int nread(),mread(),Xread(),Yread();printf(%.11Lf\n,solve.expectedTime(n,m,X,Y));return 0;
}
*/
