海亮2月14日
T1
题意
传奇特级大师 \(\mathsf E \color{red}\mathsf{ntropyIncreaser}\) 有一个 \(n\times m\) 的矩形纸片，她将其放置在一个平面直角坐标系中，使其左下角在 \((0,0)\)，右上角在 \((n,m)\) 位置。
她每次会均匀随机选择一条平行于坐标轴、经过坐标均为整数的点，且穿过（不能是经过边界）纸片的直线，沿此方向将纸片裁开，并扔掉裁剪线的下侧或右侧的部分。
她想要你求出期望多少次操作后，剩下纸片的面积小于 \(k\)。你只需要求出答案模 \(10^9+7\) 的结果。
有多组数据，每次给出 \(n,m,k\)，保证所有 \(n\) 之和、所有 \(m\) 之和不超过 \(10^6\)。
题解
考虑将选择顺序看作一个排列，然后看哪些位置是有效的。
我们发现，一个横（竖）线 \(i\) 有效当且仅当以下两个条件都成立：
- 排在 \(i\) 前面的横（竖）线没有在 \([1,i-1]\) 范围内的。
- 排在 \(i\) 前面的竖（横）线没有在 \([1,\lfloor\frac{S}{i}\rfloor]\) 范围内的。
发现出现这种情况的概率是 \(\frac{1}{i}\times\frac{1}{\min(n,\frac{S}{i})}\) 的（这里算的是横线，竖线记得换下 \(n\)）。
然后枚举一下就好了。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e6 + 10, mod = 1e9 + 7;
int inv[maxn];
int qpow(int x,int a){
int res = 1;
while(a){
if(a & 1)res = 1ll * res * x % mod;
x = 1ll * x * x % mod;a >>= 1;
}
return res;
}
int n, m, S;
void main(){
inv[1] = 1;
for(int i = 2;i < maxn;i++){inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;}
auto solve = [](){
n = read(); m = read(); S = read() - 1;
if(n * m <= S){puts("0");return;}
int ans = 1;
for(int i = 1;i < n;i++){
int j = min(S / i,m);if(j == m)continue;
ans += inv[i + j];if(ans >= mod)ans -= mod;
}
for(int i = 1;i < m;i++){
int j = min(S / i,n);if(j == n)continue;
ans += inv[i + j];if(ans >= mod)ans -= mod;
}
printf("%lld\n",ans);
return;
};
int T = read();while(T--)solve();
return;
}
};
bool edmemory;
signed main(){
// freopen("tmp.in","r",stdin);
auto stclock = clock();
Call_me_Eric::main();
auto edclock = clock();
cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
return 0;
}