《CF708E Student‘s Camp》
题目描述
Alex 学习刻苦，赢得了前往位于海边的学生营地 Alushta 的旅行机会。
不幸的是，现在正值大风期，营地有可能被毁坏！营地建筑可以看作是由 n+2 层高、m 列宽的混凝土块组成的矩形。
每天都有来自海上的微风。每一块（除了最上层和最下层的那些），如果它左边没有块，则会以概率 p 被摧毁。同理，每晚微风会朝向大海吹去。于是，每一块（同样除了最上层和最下层的那些），如果其右侧没有块，也会以相同的概率 p 被摧毁。注意，最上层和最下层的混凝土块是不可摧毁的，因此只有 n⋅m 个块有可能被摧毁。
强风期会持续 k 天与 k 夜。如果在此期间，建筑分裂成至少两个连通块，则会倒塌，Alex 只能另找地方度过夏天。
请你计算，Alex 不必另寻他处、能够顺利于该营地度夏的概率。
输入格式
第一行包含两个整数 n 和 m（1≤n,m≤1500），表示建筑可被摧毁部分的尺寸。
第二行包含两个整数 a 和 b（1≤a≤b≤109），定义概率 p。保证 a 和 b 互质。
第三行包含一个整数 k（0≤k≤100000）——表示大风将持续的天数和夜数。
输出格式
假设答案为最简分数 yx，请输出一个整数 z，使得 0≤z<109+7，且满足 z≡x×y−1(mod109+7)。保证在数据范围内上述数一定存在。
显示翻译
题意翻译
输入输出样例
输入 #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(109+7)=937500007。
由 ChatGPT 5 翻译
代码实现;
#include<bits/stdc++.h> using namespace std; const int N=1.5e3+10; const int S=1e5+10; const int mod=1e9+7; 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 res=1) { for (;b;b>>=1,a=mul(a,a)) if (b & 1) res=mul(res,a); return res; } void fma(int &x,int y,int z) { x = ((ll)y*z+x)%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 i=2;i<S;++i) { fac[i]=mul(fac[i-1],i); inv[i]=mul(inv[mod%i],mod-mod/i); } for (int i=2;i<S;++i) inv[i]=mul(inv[i-1],inv[i]); scanf("%d%d",&n,&m); int a,b; scanf("%d%d",&a,&b); int P=pow(b,mod-2,a); scanf("%d",&k); for (int i=0;i<=m && i<=k;++i) p[i]=pow(P,i,pow(1+mod-P,k-i,C(k,i))); for (int i=0;i<=m;++i) red(pre[i]=p[i]+(i ? pre[i-1]-mod : 0)); f[0][m]=1; for (int i=1;i<=n;++i) { static int tp[N],ts[N]; for (int j=1;j<=m;++j) { red(tp[j]=tp[j-1]+f[i-1][j]-mod); fma(ts[j]=ts[j-1],p[j],tp[j]); } for (int r=1;r<=m;++r) { int sm=mul(pre[r-1],tp[m]-tp[m-r]+mod); red(sm-=ts[r-1]); f[i][r]=mul(p[m-r],sm); } } int ans=0; for (int i=1;i<=m;++i) red(ans+=f[n][i]-mod); printf("%d\n",ans); return 0; }