### \[ABC154F\] Many Many Paths
この問題は組み合わせ数を使用します。簡単な問題ですが、詳細な解説は後日行います。
### CF1542D
この問題では動的計画法（DP）を使用します。問題文を変換すると、各操作 \(+x\) に対して、その操作が加算されるためには、それより小さい操作が必要であることがわかります。つまり、操作の具体的な値ではなく、その大小関係に注目します。\(dp[i][j]\) を、最初の \(i\) 個の操作の中で、\(x\) より小さい加算操作が \(j\) 個あるときの部分列の数と定義します。そして、遷移を分類して考えることができます。
### AT\_tenka1\_2017\_f
この数論の問題については、洛谷で解説を書きましたので、そちらを参照してください。不明な点があれば補完してください。
### P5505
直接合法な配置の数を求めるのは難しいので、補集合を考えます。全配置の数から不合法な配置の数を引きます。全配置の数は \(\prod_{i=1}^m C(n-1, n+a_i-1)\) です。次に、空の箱が \(x\) 個ある場合の貢献を計算します。これは、球を \(n-x\) 個の箱に入れる方法であり、貢献は \(C(n-x-1, n-x+a_i-1)\) です。乗法原理により、\(i\) 個の箱が空の場合の貢献は \(C(i, n) \times \prod_{j=1}^m C(n-i-1, n-i+a_j-1)\) となります。ただし、大きな \(x\) の貢献には小さな \(x\) の貢献が含まれているため、単純に差し引くことはできません。正しい方法は包除原理を使用することです。空の箱が \(x\) 個ある場合の貢献を \(f_x\) とすると、答えは \(ans = f_0 - f_1 + f_2 - \ldots + (-1)^{n-1} \times f_{n-1}\) となります。
### P4113
データ範囲が \(2 \times 10^6\) なので、モーのアルゴリズムは使えません。対数時間のアルゴリズムが必要です。まず、クエリを右端 \(r\) でソートしてオフラインで処理します。各点が同じ色を持つ次の点への貢献を考えます。初めて色 \(c\) が現れたときは貢献がありませんが、2回目以降は貢献があります。そのため、各点の前後の同じ色の点を記録し、木の配列を使用して貢献を管理します。
コードを見る
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 114514, M = 1919810, mod = 1e9 + 7;
ll n, m, a[N], inv[N];
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll C(ll n, ll m) {
ll ans = 1, res = 1;
for (int i = m + 1; i <= n; ++i) ans = ans * i % mod;
for (int i = 1; i <= n - m; ++i) res = res * i % mod;
return ans * qpow(res, mod - 2) % mod;
}
ll ans, res, f[2005][2005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> a[i];
for (int i = 0; i <= 2000; ++i) f[i][0] = f[i][i] = 1;
for (int i = 1; i <= 2000; ++i)
for (int j = 1; j <= i; ++j)
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
for (int i = 0; i < n; ++i) {
res = qpow(-1, i) * f[n][i] % mod;
for (int j = 1; j <= m; ++j)
res = res * f[n - i + a[j] - 1][n - i - 1] % mod;
ans = ((ans + res) % mod + mod) % mod;
}
cout << ans;
return 0;
}
コードを見る
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 114514, M = 2 * 1919810;
ll n, cl, m, a[M], ans[M];
ll las[M], lasc[M];
ll c[M];
ll lowbit(ll x) { return x & -x; }
void update(ll x, ll k) {
if (!x) return;
while (x <= n) {
c[x] += k;
x += lowbit(x);
}
}
ll query(ll x) {
if (!x) return 0;
ll ans = 0;
while (x) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}
struct que {
ll l, r, id;
} q[M];
bool cmp(que x, que y) {
return x.r < y.r;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> cl >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
las[i] = lasc[a[i]];
lasc[a[i]] = i;
}
for (int i = 1; i <= m; ++i) cin >> q[i].l >> q[i].r, q[i].id = i;
sort(q + 1, q + m + 1, cmp);
ll pos = 1;
for (int i = 1; i <= n; ++i) {
update(las[i], 1), update(las[las[i]], -1);
while (q[pos].r == i && pos <= m) {
ans[q[pos].id] = query(q[pos].r) - query(q[pos].l - 1);
++pos;
}
}
for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
return 0;
}