#include <bits/stdc++.h>

using namespace std;

const int N = 223456;
const int P = (int) 1e9 + 9;

int n, m, f[N], g[N], inv[N], fact[N], inv_fact[N];

int binom(int x, int y) {
return (long long) fact[x] * inv_fact[y] % P * inv_fact[x - y] % P;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long long) (P - P / i) * inv[P % i] % P;
}
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= n; ++i) {
fact[i] = (long long) fact[i - 1] * i % P;
inv_fact[i] = (long long) inv_fact[i - 1] * inv[i] % P;
}
n -= m;
if (n < 0) {
cout << 0 << "\n";
return 0;
}
f[0] = 1;
for (int i = 0; 1 << (i + 1) <= n; ++i) {
for (int j = 0; j <= (m + 1) / 2; j += 2) {
for (int k = j << i; k <= n; ++k) {
g[k] = ((long long) f[k - (j << i)] * binom((m + 1) / 2, j) + g[k]) % P;
}
}
for (int j = 0; j <= n; ++j) {
f[j] = g[j];
g[j] = 0;
}
}
int ans = binom(n + m, m);
for (int i = 0; i <= n; ++i) {
ans = (ans - (long long) f[i] * binom(n - i + m / 2, m / 2) % P + P) % P;
}
cout << ans << "\n";
return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 223456;
const int P = (int) 1e9 + 9;

int n, m, f[N], g[N], inv[N], fact[N], inv_fact[N];

int binom(int x, int y) {
return (long long) fact[x] * inv_fact[y] % P * inv_fact[x - y] % P;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long long) (P - P / i) * inv[P % i] % P;
}
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= n; ++i) {
fact[i] = (long long) fact[i - 1] * i % P;
inv_fact[i] = (long long) inv_fact[i - 1] * inv[i] % P;
}
n -= m;
if (n < 0) {
cout << 0 << "\n";
return 0;
}
f[0] = 1;
for (int i = 0; 1 << (i + 1) <= n; ++i) {
for (int j = 0; j <= (m + 1) / 2; j += 2) {
for (int k = j << i; k <= n; ++k) {
g[k] = ((long long) f[k - (j << i)] * binom((m + 1) / 2, j) + g[k]) % P;
}
}
for (int j = 0; j <= n; ++j) {
f[j] = g[j];
g[j] = 0;
}
}
int ans = binom(n + m, m);
for (int i = 0; i <= n; ++i) {
ans = (ans - (long long) f[i] * binom(n - i + m / 2, m / 2) % P + P) % P;
}
cout << ans << "\n";
return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 223456;
const int P = (int) 1e9 + 9;

int n, m, f[N], g[N], inv[N], fact[N], inv_fact[N];

int binom(int x, int y) {
return (long long) fact[x] * inv_fact[y] % P * inv_fact[x - y] % P;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long long) (P - P / i) * inv[P % i] % P;
}
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= n; ++i) {
fact[i] = (long long) fact[i - 1] * i % P;
inv_fact[i] = (long long) inv_fact[i - 1] * inv[i] % P;
}
n -= m;
if (n < 0) {
cout << 0 << "\n";
return 0;
}
f[0] = 1;
for (int i = 0; 1 << (i + 1) <= n; ++i) {
for (int j = 0; j <= (m + 1) / 2; j += 2) {
for (int k = j << i; k <= n; ++k) {
g[k] = ((long long) f[k - (j << i)] * binom((m + 1) / 2, j) + g[k]) % P;
}
}
for (int j = 0; j <= n; ++j) {
f[j] = g[j];
g[j] = 0;
}
}
int ans = binom(n + m, m);
for (int i = 0; i <= n; ++i) {
ans = (ans - (long long) f[i] * binom(n - i + m / 2, m / 2) % P + P) % P;
}
cout << ans << "\n";
return 0;
}

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define p 1000000009
#define md(_o) (((_o) >= p) ? ((_o)-p) : (_o))
using namespace std;
namespace ywy {
inline ll mi(int a, int b) {
ll ans = 1, tmp = a;
while (b) {
if (b & 1)
ans = (ans * tmp) % p;
tmp = (tmp * tmp) % p;
b >>= 1;
}
return (ans);
}
ll jc[200001], jcny[200001];
inline ll cnm(int n, int m) {
if (n < m || m < 0)
return (0);
ll cjr = jc[n];
cjr *= jcny[m];
cjr %= p;
cjr *= jcny[n - m];
return (cjr % p);
}
inline ll chaban(int n, int m) {
if (n == 0 && m == 0)
return (1);
return (cnm(n + m - 1, m - 1));
}
ll dp[21][150001];
inline void pre(int n) {
jc[0] = 1;
for (register int i = 1; i <= n; i++) jc[i] = (jc[i - 1] * i) % p;
jcny[n] = mi(jc[n], p - 2);
for (register int i = n - 1; i >= 0; i--) jcny[i] = (jcny[i + 1] * (i + 1)) % p;
}
void ywymain() {
int n, m;
cin >> n >> m;
if (n < m) {
cout << 0 << endl;
return;
}
pre(n + m);
int k = 1;
while ((1 << k) <= n) k++;
dp[k][n - m] = 1;
for (register int i = k - 1; i >= 0; i--) {
for (register int j = 0; j <= n - m; j++) {
if (!dp[i + 1][j])
continue;
for (register int k = 0; k <= (m + 1) / 2 && k * (1 << i) <= j; k += 2) {
dp[i][j - k * (1 << i)] = (dp[i][j - k * (1 << i)] + dp[i + 1][j] * cnm((m + 1) / 2, k)) % p;
}
}
}
ll ans = 0;
for (register int i = 0; i <= n - m; i++) ans = (ans + dp[0][i] * chaban(i, (m + 2) / 2)) % p;
cout << (cnm(n, m) + p - ans) % p << endl;
}
}
int main() {
ywy::ywymain();
return (0);
}

我的第2篇题解

#include <iostream>

using namespace std;

int main()
{
int a, b;
cin >> a >> b;
cout << a + b << endl;
}