域名没备案如何建设网站,郑州seo优化外包顾问阿亮,流量网站,辽宁建设工程信息网网站P3706 [SDOI2017]硬币游戏
题目描述
Solution
前置技能#xff1a; P4548 [CTSC2006]歌唱王国 歌唱王国就是n1n1n1的情况。
我们用类似的方法#xff0c;先考虑两个串的情况。
设SAS_ASA表示AAA串最先选到的概率#xff0c;设SBS_BSB表示BBB串最先选到的概率。
则…P3706 [SDOI2017]硬币游戏
题目描述
Solution
前置技能 P4548 [CTSC2006]歌唱王国 歌唱王国就是n1n1n1的情况。
我们用类似的方法先考虑两个串的情况。
设SAS_ASA表示AAA串最先选到的概率设SBS_BSB表示BBB串最先选到的概率。
则有 NSA∑2k[A(k)A(k)]SB∑2k[B(k)A(k)]NSA∑2k[A(k)B(k)]SB∑2k[B(k)B(k)]NSASB1NS_A\sum2^k[A^{(k)}A_{(k)}]S_B\sum2^k[B^{(k)}A_{(k)}]\\ NS_A\sum2^k[A^{(k)}B_{(k)}]S_B\sum2^k[B^{(k)}B_{(k)}]\\ NS_AS_B1 NSA∑2k[A(k)A(k)]SB∑2k[B(k)A(k)]NSA∑2k[A(k)B(k)]SB∑2k[B(k)B(k)]NSASB1 因此可以高斯消元求出两个串的答案。 AnsASASASBAnsBSBSASBAns_A\frac{S_A}{S_AS_B}\;\;\;\; Ans_B\frac{S_B}{S_AS_B} AnsASASBSAAnsBSASBSB
而拓展到nnn个串也是一样的。
NSA∑2k[A(k)A(k)]SB∑2k[B(k)A(k)]...NSA∑2k[A(k)B(k)]SB∑2k[B(k)B(k)]...NSA∑2k[A(k)C(k)]SB∑2k[B(k)C(k)]......NSASBSC...1NS_A\sum2^k[A^{(k)}A_{(k)}]S_B\sum2^k[B^{(k)}A_{(k)}]...\\ NS_A\sum2^k[A^{(k)}B_{(k)}]S_B\sum2^k[B^{(k)}B_{(k)}]...\\ NS_A\sum2^k[A^{(k)}C_{(k)}]S_B\sum2^k[B^{(k)}C_{(k)}]...\\ ...\\ NS_AS_BS_C...1 NSA∑2k[A(k)A(k)]SB∑2k[B(k)A(k)]...NSA∑2k[A(k)B(k)]SB∑2k[B(k)B(k)]...NSA∑2k[A(k)C(k)]SB∑2k[B(k)C(k)]......NSASBSC...1 高斯消元O(n3)O(n^3)O(n3)求解即可。
代码里直接把NNN代到上面的式子里了因此只有大小为n∗(n1)n*(n1)n∗(n1)的矩阵。
#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 double eps1e-10;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e99;
const int MAXN305;
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;
}
char st[MAXN];
double pow2[MAXN],a[MAXN][MAXN];
int hsh[MAXN][MAXN],Pw[MAXN];
inline int upd(int x,int y){ return xymods?xy-mods:xy; }
inline int gethash(int n,int l,int r) { return upd(hsh[n][r],mods-1ll*Pw[r-l1]*hsh[n][l-1]%mods); }
inline 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 main()
{int nread(),mread();pow2[0]1,Pw[0]1;for (int i1;im;i) pow2[i]pow2[i-1]*2,Pw[i]1ll*Pw[i-1]*MAXN%mods;for (int i0;in;i){scanf(%s,st1);for (int j1;jm;j) hsh[i][j](1ll*hsh[i][j-1]*MAXN(st[j]T?1:2))%mods;}for (int i0;in;i){for (int j0;jn;j)for (int k1;km;k)if (gethash(i,1,k)gethash(j,m-k1,m)) a[i][j]pow2[k];for (int j0;jn;j) a[i][j]--;a[i][n]1;} solve(n);double sum0;for (int i0;in;i) suma[i][n];for (int i0;in;i) printf(%.10lf\n,a[i][n]/sum);return 0;
}
