文章目录
题目分析错因代码
题目
[NOI Online #2 入门组] 建设城市
分析
正整数
x
1
,
x
2
,
⋯
,
x
n
x_1, x_2, \cdots, x_n
x1,x2,⋯,xn 满足
1
≤
x
1
≤
x
2
≤
⋯
≤
x
n
≤
r
1 \leq x_1 \leq x_2 \leq \cdots \leq x_n \leq r
1≤x1≤x2≤⋯≤xn≤r，则
x
1
,
x
2
,
⋯
,
x
n
x_1, x_2, \cdots, x_n
x1,x2,⋯,xn 的取值方案数为
C
n
+
r
−
1
r
−
1
C_{n + r - 1}^{r - 1}
Cn+r−1r−1。证明：将问题转化为构造一个序列
k
1
,
k
2
,
⋯
,
k
r
k_1, k_2, \cdots, k_r
k1,k2,⋯,kr 表示
[
1
,
r
]
[1, r]
[1,r] 中每个数在
x
x
x 中出现了多少次，则
k
k
k 与
x
x
x 一一对应，我们只需要求
k
k
k 的取值方案数，
k
k
k 需满足的条件是
k
1
+
k
2
+
⋯
+
k
r
=
n
k_1 + k_2 + \cdots + k_r = n
k1+k2+⋯+kr=n 且
k
1
,
k
2
,
⋯
,
k
r
∈
[
0
,
n
]
k_1, k_2, \cdots, k_r \in [0, n]
k1,k2,⋯,kr∈[0,n]，插空法得
k
k
k 的方案数为
C
n
+
r
−
1
r
−
1
C_{n + r - 1}^{r - 1}
Cn+r−1r−1。
然后枚举
x
,
y
x, y
x,y 的高度计算方案数即可。
错因
想到
x
x
x 转化为
k
k
k 的时候考试仅剩十几分钟了，推出
C
n
+
r
−
1
r
−
1
C_{n + r - 1}^{r - 1}
Cn+r−1r−1 的时候还有 3 分钟考试结束；预处理阶乘的时候要处理到
m
+
n
m + n
m+n 而不是
n
n
n（最后一分钟过了第一个样例第二个样例出 0，如果多 3 分钟就能发现这个问题但是没有时间了，导致 100 pts
→
\to
→ 0 pts）；
代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
const int MOD
= 998244353;
const int MAXN
= 100000;
int M
, N
, X
, Y
;
int Fac
[2 * MAXN
+ 5], Inv
[2 * MAXN
+ 5];
inline int Mul(const int &x
, const int &y
) {
return (long long)x
* y
% MOD
;
}
inline int Add(int x
, const int &y
) {
x
+= y
; if (x
>= MOD
) x
-= MOD
; return x
;
}
int Pow(int x
, int y
) {
int ret
= 1;
while (y
) {
if (y
& 1)
ret
= Mul(ret
, x
);
x
= Mul(x
, x
);
y
>>= 1;
}
return ret
;
}
int C(int n
, int m
) {
return Mul(Fac
[n
], Mul(Inv
[m
], Inv
[n
- m
]));
}
int Cal(int rgt
, int n
) {
return C(n
+ rgt
- 1, rgt
- 1);
}
int main() {
scanf("%d%d%d%d", &M
, &N
, &X
, &Y
);
Fac
[0] = 1;
for (int i
= 1; i
<= M
+ N
; i
++)
Fac
[i
] = Mul(Fac
[i
- 1], i
);
Inv
[M
+ N
] = Pow(Fac
[M
+ N
], MOD
- 2);
for (int i
= M
+ N
- 1; i
>= 0; i
--)
Inv
[i
] = Mul(Inv
[i
+ 1], i
+ 1);
if (X
> N
) {
int tmp
= 2 * N
- Y
+ 1;
Y
= 2 * N
- X
+ 1;
X
= tmp
;
}
if (Y
<= N
) {
int Ans
= 0, R
= Cal(M
, N
);
for (int i
= 1; i
<= M
; i
++)
Ans
= Add(Ans
, Mul(R
, Mul(Cal(i
, X
- 1), Cal(M
- i
+ 1, N
- Y
))));
printf("%d", Ans
);
}
else {
int Ans
= 0;
for (int i
= 1; i
<= M
; i
++) {
Ans
= Add(Ans
, Mul(Mul(Cal(i
, X
- 1), Cal(M
- i
+ 1, N
- X
)), Mul(Cal(i
, 2 * N
- Y
), Cal(M
- i
+ 1, Y
- N
- 1))));
}
printf("%d", Ans
);
}
return 0;
}
