解きます
解く
$a$の要素は全て異なるので, $b$の組み合わせを調べてそれを$N!$倍することで求めます.
一旦, $b_1$が奇数だと仮定します.
定義されていない$b_0$を$0$, $b_{N+1}$を$N$が偶数なら$2\left\lfloor\frac M2\right\rfloor+1$, $N$が奇数なら$2\left\lceil\frac M2\right\rceil$とし, 更に$c_i:=\frac{b_i-b_{i-1}-1}2$とすると, $c$の要素は$b$の性質から全て非負整数になり, また, $c_1$から$c_{N+1}$までの総和は
$$\begin{align}
\frac{b_{N+1}-(N+1)}2
&=\begin{cases}
\left\lfloor\frac M2\right\rfloor-\frac N2 &\text{if } 2 \mid N \\
\left\lceil\frac M2\right\rceil-\frac{N+1}2 &\text{if } 2 \nmid N \\
\end{cases}\\
&=\left\lfloor\frac{M-N}2\right\rfloor
\end{align}$$
になります.
という訳で, 長さ$N+1$総和$\left\lfloor\frac{M-N}2\right\rfloor$の数列の組合せ数を求める問題になりました. 公式を使って答えは
$$
\binom{\left\lfloor\frac{M-N}2\right\rfloor+N}N
= \binom{\left\lfloor\frac{M+N}2\right\rfloor}N
$$
です.
...これは$b_1$が奇数だと仮定した場合です. $b_1$が偶数の場合も同様にやると, $b_0=-1$, $b_{N+1}$は$N$が偶数のときは$2\left\lceil\frac M2\right\rceil$, 奇数のときは$2\left\lfloor\frac M2\right\rfloor+1$として, $c$の総和が
$$\begin{align}
\frac{b_{N+1}+1-(N+1)}2
&=\begin{cases}
\left\lceil\frac M2\right\rceil-\frac N2 &\text{if } 2 \mid N \\
\left\lfloor\frac M2\right\rfloor-\frac{N-1}2 &\text{if } 2 \nmid N \\
\end{cases}\\
&=\left\lceil\frac{M-N}2\right\rceil
\end{align}$$
になるので, この場合は
$$
\binom{\left\lceil\frac{M-N}2\right\rceil+N}N
= \binom{\left\lceil\frac{M+N}2\right\rceil}N
$$
通りになります.
$b_0$が奇数の場合, 偶数の場合それぞれ求めたので, この2つを足して$N!$を掛けたら答えになります.
... あれ, FPSを使いませんでした. まあそういう日もあります
use ac_library::*;
use proconio::*;
type Mint = ModInt998244353;
fn main() {
input! {
n: usize,
m: usize,
}
// 階乗テーブル
let factorial = {
let mut r = vec![Mint::raw(1)];
for i in 1..=400000 {
r.push(r[i - 1] * i);
}
r
};
// 二項係数
let binom = |a: usize, b: usize| {
if b > a {
Mint::raw(0)
} else {
factorial[a] / (factorial[b] * factorial[a - b])
}
};
println!(
"{}",
(binom((m + n) / 2, n) + binom((m + n + 1) / 2, n)) * factorial[n]
);
}
提出(4 ms):
FPSを使う
折角なので解説を見てFPSを使った解法を勉強しましょう. $b$を数え上げて$N!$倍するのは一緒です.
差を見るのも一緒ですね. $b_0 = 0$, $b_{N+1}=M$で, $c_k=b_{k+1}-b_{k}$とすると,
- $c_0$, $c_N$は非負整数
- $c_1, c_2, ..., c_{N-1}$は正の奇数
- $\sum_{k=0}^N c_k=M$
の条件を満たす数え上げになります.
という訳で答えが
$$N!\left[x^M\right]\left(\frac1{1-x}\right)^2\left(\frac x{1-x^2}\right)^{N-1}$$
ですね. $\frac1{1-x}$が非負整数, $\frac x{1-x^2}$が正の奇数に対応します.
とりあえず$x$を掛けてる部分を消して
$$N!\left[x^{M-N+1}\right]\left(\frac1{1-x}\right)^2\left(\frac1{1-x^2}\right)^{N-1}$$
のように変形します.
$$\left[x^A\right]\left(\frac1{1-x}\right)^2=A+1$$
$$\left[x^B\right]\left(\frac1{1-x^2}\right)^{N-1}=\begin{cases}
\binom{(B\div2)+N-2}{N-2} &\text{if } 2 \mid B \\
0 &\text{if } 2 \nmid B \\
\end{cases}$$
昨日と同じ要領で$O(M+N)$ (階乗テーブルを作る時間を除けば$O(M-N)$)で解けます.
use ac_library::*;
use proconio::*;
type Mint = ModInt998244353;
fn main() {
input! {
n: usize,
m: usize,
}
// 求めるものが負次の項になるケースの除外
if n > m + 1 {
println!("0");
return;
}
// 37行目でn - 2という値を使うが, これが負になるケースを除外
if n == 1 {
println!("{}", n + 1);
return;
}
// 階乗テーブル
let factorial = {
let mut r = vec![Mint::raw(1)];
for i in 1..=400000 {
r.push(r[i - 1] * i);
}
r
};
// 二項係数
let binom = |a: usize, b: usize| factorial[a] / (factorial[b] * factorial[a - b]);
let mut ans = Mint::raw(0);
// 右側の因子の係数が0にならない次数を列挙
for b in (0..=m + 1 - n).step_by(2) {
let a = m + 1 - n - b;
let lhs = Mint::new(a + 1);
let rhs = binom(b / 2 + n - 2, n - 2);
ans += lhs * rhs;
}
println!("{}", ans * factorial[n]);
}
提出(13 ms):
終わり
切り上げたり切り捨てたりで計算ミスを連発して正しい式を求めるまで3時間くらいかかってました.
以上です