1 条题解
-
0昌孝阳 (changxiaoyang) LV 10 @ 2023-10-1 16:46:12
来了
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int maxn = 2e5 + 7; ll f[maxn],fac[maxn],inv[maxn]; struct P { ll x,y; }p[maxn]; ll qpow(ll x,ll n) { ll res = 1; while(n) { if(n & 1) res = (res * x) % mod; x = (x * x) % mod; n >>= 1; } return res; } void init() { fac[0] = inv[0] = 1; for(int i = 1;i < maxn;i++) { fac[i] = fac[i - 1] * i % mod; inv[i] = qpow(fac[i],mod - 2); } } ll C(ll n,ll m) { ll s1 = fac[n]; ll s2 = inv[n - m]; ll s3 = inv[m]; return (s1 * s2) % mod * s3 % mod; } int cmp(P a,P b) { if(a.x == b.x)return a.y < b.y; return a.x < b.x; } int main() { init(); ll h,w,n; cin >> h >> w >> n; for(int i = 1;i <= n;i++) { ll x,y;scanf("%lld%lld",&x,&y); p[i].x = x;p[i].y = y; } p[++n].x = h;p[n].y = w; sort(p + 1,p + 1 + n,cmp); for(int i = 1;i <= n;i++) { ll res = C(p[i].x + p[i].y - 2,p[i].x - 1); for(int j = 1;j < i;j++) { if(p[j].x > p[i].x || p[j].y > p[i].y)continue; res -= f[j] * C(p[i].x - p[j].x + p[i].y - p[j].y,p[i].x - p[j].x); res = (res + mod) % mod; } f[i] = (res + mod) % mod; } printf("%lld\n",f[n]); return 0; }
- 1
信息
- ID
- 217
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 6
- 上传者