AtCoder Beginner Contest 042

AtCoder Beginner Contest 042D - Iroha and a GridDescription有一个h⋅wh \cdot wh⋅w网格yunayu 要从(1,1)(1, 1)(1,1)走到(h,w)(h, w)(h,w)每次她可以选择向下走一格或向右走一格然而不能经过左下角a⋅ba \cdot ba⋅b区域的任何格子。她共有多少种走法Solution咕本来想到的写法和标程一样但写着写着想起来饭老师之前在群里说过的一个 trick然后非常优雅的过了“如果不经过黄格必经过某一个红箭头。”而且如果只能向下或向右走那么通过每一个红箭头的路径一定不重叠保证了加法原理的正确性那么对于本题我们只要枚举必经的斜着的一条线上的点即可Codeint h, w, a, b, nx[_]; int C(int a, int b) { if(ab) return 0; return nx[a]*inv(nx[b])%_m*inv(nx[a-b])%_m; } void solve() { cinhwab; int yuh-ab1, __0; for(int ib1; iw; i) { int xyu-i, yi; if(!x) break; __(__C(x-1y-1, x-1)*C(h-xw-y, h-x))%_m; } cout__\n; } //yunayu_2026_target_M signed main() { cin.tie(0)-sync_with_stdio(0); nx[0]1; for(int i1; i200005; i) { nx[i]nx[i-1]*i%_m; } solve(); // int T; cinT; while(T--) solve(); return 0; } //日拱一卒功不唐捐。云遥栈“日拱一卒功不唐捐。”