题目描述Alex 学习刻苦赢得了前往位于海边的学生营地 Alushta 的旅行机会。不幸的是现在正值大风期营地有可能被毁坏营地建筑可以看作是由 n2 层高、m 列宽的混凝土块组成的矩形。每天都有来自海上的微风。每一块除了最上层和最下层的那些如果它左边没有块则会以概率 p 被摧毁。同理每晚微风会朝向大海吹去。于是每一块同样除了最上层和最下层的那些如果其右侧没有块也会以相同的概率 p 被摧毁。注意最上层和最下层的混凝土块是不可摧毁的因此只有 n⋅m 个块有可能被摧毁。强风期会持续 k 天与 k 夜。如果在此期间建筑分裂成至少两个连通块则会倒塌Alex 只能另找地方度过夏天。请你计算Alex 不必另寻他处、能够顺利于该营地度夏的概率。输入格式第一行包含两个整数 n 和 m1≤n,m≤1500表示建筑可被摧毁部分的尺寸。第二行包含两个整数 a 和 b1≤a≤b≤109定义概率 p。保证 a 和 b 互质。第三行包含一个整数 k0≤k≤100000——表示大风将持续的天数和夜数。输出格式假设答案为最简分数 yx​请输出一个整数 z使得 0≤z1097且满足 z≡x×y−1(mod1097)。保证在数据范围内上述数一定存在。显示翻译题意翻译输入输出样例输入 #1复制2 2 1 2 1输出 #1复制937500007输入 #2复制5 1 3 10 1输出 #2复制95964640输入 #3复制3 3 1 10 5输出 #3复制927188454说明/提示在第一个样例中四块砖每块被摧毁的概率为 21​。有 7 种情况不会使建筑倒塌所求概率为 167​因此应输出 7×16−1mod(1097)937500007。由 ChatGPT 5 翻译代码实现;#includebits/stdc.h using namespace std; const int N1.5e310; const int S1e510; const int mod1e97; typedef long long ll; void red(int x) { x x 31 mod; } int mul(int a,int b) { return (ll)a*b%mod; } int pow(int a,int b,int res1) { for (;b;b1,amul(a,a)) if (b 1) resmul(res,a); return res; } void fma(int x,int y,int z) { x ((ll)y*zx)%mod; } int n,m,k; int p[N],pre[N]; int fac[S],inv[S]; int C(int a,int b) { return (ll)fac[a]*inv[b]%mod*inv[a-b]%mod; } int f[N][N]; int main() { fac[0]fac[1]inv[0]inv[1]1; for (int i2;iS;i) { fac[i]mul(fac[i-1],i); inv[i]mul(inv[mod%i],mod-mod/i); } for (int i2;iS;i) inv[i]mul(inv[i-1],inv[i]); scanf(%d%d,n,m); int a,b; scanf(%d%d,a,b); int Ppow(b,mod-2,a); scanf(%d,k); for (int i0;im ik;i) p[i]pow(P,i,pow(1mod-P,k-i,C(k,i))); for (int i0;im;i) red(pre[i]p[i](i ? pre[i-1]-mod : 0)); f[0][m]1; for (int i1;in;i) { static int tp[N],ts[N]; for (int j1;jm;j) { red(tp[j]tp[j-1]f[i-1][j]-mod); fma(ts[j]ts[j-1],p[j],tp[j]); } for (int r1;rm;r) { int smmul(pre[r-1],tp[m]-tp[m-r]mod); red(sm-ts[r-1]); f[i][r]mul(p[m-r],sm); } } int ans0; for (int i1;im;i) red(ansf[n][i]-mod); printf(%d\n,ans); return 0; }