面白い！！！！！！！！！

問題概要

長さ $N$ の整数列 $A_1, A_2, \dots, A_N$ であって、

$1 \le A_1 \le A_2 \le \dots \le A_N \le M$
$D_1 \le A_{i+1} - A_i \le D_2$

を満たすものの個数を 1000000007 で割ったあまりを求めよ。

制約

$2 \le N \le 3 × 10^{5}$
$1 \le M \le 10^{6}$

まずは変数変換

まずは数列 $A_i$ の差分に注目してみることにする。 $B_{i} = A_{i} - A_{i-1}$ とする ( $A_0 = 0$ とする)。そうすると、条件は

$B_1 + B_2 + \dots + B_N \le M$
$B_1 \ge 1$
$D_1 \le B_i \le D_2$ ( $i \ge 2$ )

という風になる。さらに、 $D_1 \le B_i \le D_2$ において $D_1 \le B_i$ のところが扱いづらいのでさらなる変数変換を行う！！！

$C_1 = B_1 - 1$
$C_i = B_i - D_1$ ( $i \ge 2$ )

とおくと、

$C_1 + C_2 + \dots + C_N \le x$ ( $x = M - 1 - D_{1} (N-1)$ とおく)
$C_i \ge 0$
$C_i \le D$ ( $i \ge 2$ 、 $D = D_2 - D_1$ とおく)

となる。さらに便宜的に $C_{N+1} \ge 0$ として、

$C_{1} + C_{2} + \dots + C_{N} + C_{N+1} = x$
$C_i \ge 0$
$C_i \le D$ ( $i \ge 2$ )

を満たすものを求める問題と思うことができる。

包除原理へ

上記の条件を満たす場合の数は、実は $C_i \le D$ ( $i \ge 2$ ) という条件さえなければ重複組合せとして有名で、「 $x$ 個のボールと、 $N$ 個の仕切りを並べる問題」と思うことができて $C(x + N, N)$ 通りになる。

$C_i \le D_i$ という条件がとても扱いづらい！！！！！
しかし反対に余事象をとって $C_i \ge D+1$ となると途端に扱いやすくなる。そのことに目をつけると包除原理が思い浮かぶ。一般に

$i = 1$ についての条件 $Q_1$
$i = 2$ についての条件 $Q_2$
...
$i = N$ についての条件 $Q_N$
$i = N+1$ についての条件 $Q_{N+1}$

をすべて満たすようなものの個数を数え上げることが要求されている問題において、「条件 $Q_i$ はとても扱いづらいが、反対に $Q_i$ を満たさないものの個数は数えやすい」という状況では、包除原理が濃厚である。

具体的には、

全体の場合の数 (条件をまったく考えない)
- 条件を 1 個満たさない場合の数 (その 1 個以外は満たしても満たさなくても良い)
+ 条件を 2 個満たさない場合の数
- 条件を 3 個満たさない場合の数
+ 条件を 4 個満たさない場合の数
- ...

という感じに求めて行けば良い。よって我々は

条件を $p$ 個満たさない
それ以外の条件については満たしても満たさなくても良い

というものを数え上げたい。まずそのような $p$ 個を選ぶ方法は、 $C(N-1, p)$ 通りある ( $C_{1}, C_{N+1}$ については最初から条件がないことに注意)

さらに条件を満たさない $p$ 個の添字を固定したとき、条件を満たしていない添字の一つを $i$ として $C_i \ge D + 1$ となっている必要がある。これは $D + 1$ 分の下駄を履いていることになる。よって下駄を脱ぐと

$C_{1} + C_{2} + \dots + C_{N+1} = x - p(D+1)$
$C_i \ge 0$

を満たすものを数え上げる問題となる。これは $C(x - p(D+1) + N, N)$ 通りとなる。

以上をまとめると、

各 $p = 0, 1, 2, \dots, N-1$ について、 $f(p) = C(N-1, p) × C(x - p(D+1) + N, N)$ とする
$p$ が偶数のときは $f(x)$ を足し、奇数のときは $f(x)$ を引く

とすれば答えが求められる。

#include <iostream>
using namespace std;

const int MAX = 11000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(long long n, long long k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}



long long N, M, D1, D2;
long long solve() {
    long long D = D2 - D1;
    long long x = M - 1 - D1 * (N-1);
    if (x < 0) return 0;

    long long res = 0;
    for (long long p = 0; p <= N-1; ++p) {
        long long tmp = COM(N-1, p) * COM(x - p*(D+1) + N, N) % MOD;
        if (p % 2 == 0) res += tmp;
        else res += MOD - tmp;
        res %= MOD;
    }
    return res;
}

int main() {
    COMinit();
    cin >> N >> M >> D1 >> D2;
    cout << solve() << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

yukicoder No.802 だいたい等差数列

問題概要

制約

まずは変数変換

包除原理へ