Mobile gold
Title Link: luogu P5363
General idea of the topic
Give you a 1*n chessboard, and then there are m things at the beginning. Each time two people operate in turn, you can choose one thing to move to the left.
(can't fly out of the grid, can't cross anything else)
Then who can't move and lose, and then ask how many initial situations you have to win first.
thinking
First consider when the launch will win.
You can see a point moving to the left as the distance between it and the point in front of it becomes smaller, and the distance to the point behind it becomes larger. Then you can also see \ (0 \) as a point (it cannot move). If all adjacent distances are \ (0 \), you lose.
Then make one smaller and the next larger, which can be seen as moving several formulas on the left to the right, and then moving them all to the far right.
That is a ladder game, which is to have an exclusive or sum of odd stones.
It's hard to consider seeking truth (0 \).
Then consider DP, that is to put \ (n-m \) stones in the \ (m+1 \) heap, and the even heap XOR sum is \ (0 \).
The first is to violently enumerate the number of formulas used to stack \ (i \) in each stacking state, and the current XOR value, \ (mn^3 \).
Then consider XOR, just look at one person at a time, and see how many piles there are.
Set \ (f_{i,j} \) as the current processing to the \ (I \) bit, and then there are stones of \ (j \), and then enumerate how many are put, \ (nm\log n \).
Then you find that for \ (N=n-m \), for each bit of its binary, you either put an expression in this bit or put several carry bits from the low bit.
Then we can directly set \ (f_{i,j} \) to be processed to the \ (I \) bit. Currently, there are \ (j \) times to select.
Then, because if \ (j > m + 1 \) is not solved directly (it can't be finished anyway), \ (j \) is at the \ (m \) level, \ (m^2\log n \).
The specific transfer is probably as follows: \ (f_{i,2j+v-k}\leftarrow f_{i+1,j}*p_k \) (\ (v \) is \ (N \) is \ (1 \) or \ (0 \), \ (p_k \) is \ (K \) distributed to the \ (m+1 \) heap, and the even heap has an even number of schemes)
\(p_k \) can be preprocessed by directly enumerating the number of even heap \ (J \), and directly \ (c_j ^ {\ left \ lfloor \ frac {m + 1} {2} \ right \ rfloor} \ cdot C ^ {K-J} {m + 1 - \ left \ lfloor \ frac {m + 1} {2} \ right \ rfloor} \)
(\(m+1-\left\lfloor\frac{m+1}{2}\right\rfloor=\left\lfloor\frac{m+2}{2}\right\rfloor\))
Then you can actually.
But not enough (at least for a problem)
Then you find that the transfer formula can actually be seen as rolling up.
Put \ (f {I + 1, J} \) in the position of \ (a {2J + V} \) and \ (P K \) in the position of \ (B {m + 1-k} \).
Then the \ (i \) bit result of the convolution of \ (a \) and \ (b \) is \ (f_{i,i-(m-1)} \).
Then you can use any module NTT. Here you use the MTT method.
Then the complexity is \ (m\log m\log n \).
code
Normal (\ (m^2\log n \))
#include<cstdio>
#define ll long long
#define mo 1000000009
using namespace std;
int n, m;
ll jc[61], inv[61], p[61];
ll f[21][61];
ll C(int n, int m) {
if (n < m) return 0;
if (m < 0) return 0;
return jc[n] * inv[m] % mo * inv[n - m] % mo;
}
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
void init() {
jc[0] = 1;
for (int i = 1; i <= m + 1; i++) jc[i] = jc[i - 1] * i % mo;
inv[m + 1] = ksm(jc[m + 1], mo - 2);
for (int i = m; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mo;
int on = (m + 1) / 2, jn = (m + 2) / 2;
for (int k = 0; k <= m + 1; k++) {
for (int i = 0; i <= on; i += 2) {
p[k] = (p[k] + C(on, i) * C(jn, k - i) % mo) % mo;
}
}
}
int main() {
scanf("%d %d", &n, &m);
init();
f[20][0] = 1; int need = n - m;
for (int i = 19; i >= 0; i--) {
int hv = (need >> i) & 1;
for (int j = 0; j <= m + 1; j++)
for (int k = 0; k <= m + 1; k++) {
int to = 2 * j + hv - k;
if (to < 0 || to > m + 1) continue;
f[i][to] = (f[i][to] + f[i + 1][j] * p[k] % mo) % mo;
}
}
ll ans = 1;
for (int i = n - m + 1; i <= n; i++) ans = ans * i % mo;
ans = ans * inv[m];
printf("%lld", (ans - f[0][0] + mo) % mo);
return 0;
}
MTT Version (\ (m\log m\log n \))
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lim 32000
#define ll long long
#define mo 1000000009
using namespace std;
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx; y = yy;
}
};
int n, m;
ll jc[61], inv[61], p[61];
ll f[21][61], ans[201], a[201], b[201];
double Pi = acos(-1.0);
complex operator +(complex x, complex y) {
return (complex){x.x + y.x, x.y + y.y};
}
complex operator -(complex x, complex y) {
return (complex){x.x - y.x, x.y - y.y};
}
complex operator *(complex x, complex y) {
return (complex){x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x};
}
ll C(int n, int m) {
if (n < m) return 0;
if (m < 0) return 0;
return jc[n] * inv[m] % mo * inv[n - m] % mo;
}
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
void init() {
jc[0] = 1;
for (int i = 1; i <= m + 1; i++) jc[i] = jc[i - 1] * i % mo;
inv[m + 1] = ksm(jc[m + 1], mo - 2);
for (int i = m; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mo;
int on = (m + 1) / 2, jn = (m + 2) / 2;
for (int k = 0; k <= m + 1; k++) {
for (int i = 0; i <= on; i += 2) {
p[k] = (p[k] + C(on, i) * C(jn, k - i) % mo) % mo;
}
}
}
struct MTT_work {
complex p1[201 << 2], p2[201 << 2], q[201 << 2];
int limit, l_size, an[201 << 2];
void FFT(complex *now, int op) {
for (int i = 0; i < limit; i++)
if (i < an[i]) swap(now[i], now[an[i]]);
for (int mid = 1; mid < limit; mid <<= 1) {
complex Wn(cos(Pi / mid), op * sin(Pi / mid));
for (int R = (mid << 1), j = 0; j < limit; j += R) {
complex w(1, 0);
for (int k = 0; k < mid; k++, w = w * Wn) {
complex x = now[j + k], y = w * now[j + mid + k];
now[j + k] = x + y; now[j + mid + k] = x - y;
}
}
}
}
void mul(int n, ll *x, int m, ll *y) {
limit = 1; l_size = 0;
while (limit <= n + m) {
limit <<= 1; l_size++;
}
for (int i = 0; i < limit; i++) p1[i] = p2[i] = q[i] = (complex){0, 0};
for (int i = 0; i <= n; i++)
p1[i] = (complex){x[i] / lim, x[i] % lim}, p2[i] = (complex){x[i] / lim, -x[i] % lim};
for (int i = 0; i <= m; i++)
q[i] = (complex){y[i] / lim, y[i] % lim};
for (int i = 0; i < limit; i++)
an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1));
FFT(p1, 1); FFT(p2, 1); FFT(q, 1);
for (int i = 0; i < limit; i++) q[i].x /= limit, q[i].y /= limit;
for (int i = 0; i < limit; i++) p1[i] = p1[i] * q[i], p2[i] = p2[i] * q[i];
FFT(p1, -1); FFT(p2, -1);
for (int i = 0; i <= n + m; i++) {
ll a1b1 = (ll)floor((p1[i].x + p2[i].x) / 2 + 0.5) % mo;
ll a1b2 = (ll)floor((p1[i].y + p2[i].y) / 2 + 0.5) % mo;
ll a2b1 = ((ll)floor(p1[i].y + 0.5) - a1b2) % mo;
ll a2b2 = ((ll)floor(p2[i].x + 0.5) - a1b1) % mo;
ans[i] = (a1b1 * lim * lim + (a1b2 + a2b1) * lim + a2b2) % mo;
ans[i] = (ans[i] + mo) % mo;
}
}
}MTT;
int main() {
scanf("%d %d", &n, &m);
init();
f[20][0] = 1; int need = n - m;
for (int i = 19; i >= 0; i--) {
int hv = (need >> i) & 1;
// for (int j = 0; j <= m + 1; j++)
// for (int k = 0; k <= m + 1; k++) {
// int to = 2 * j + hv - k;
// if (to < 0 || to > m + 1) continue;
// f[i][to] = (f[i][to] + f[i + 1][j] * p[k] % mo) % mo;
// }
memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
for (int j = 0; j <= m + 1; j++)//Double plus carry
a[2 * j + hv] = f[i + 1][j];
for (int j = 0; j <= m + 1; j++)//Conversely, move all right m+1
b[m + 1 - j] = p[j];
MTT.mul((m + 1) * 2 + hv, a, m + 1, b);
for (int j = m + 1; j <= m + 1 + m + 1; j++)
f[i][j - (m + 1)] = ans[j];//Because b moves to the right, it moves back to the m+1 bit
}
ll answ = 1;
for (int i = n - m + 1; i <= n; i++) answ = answ * i % mo;
answ = answ * inv[m];
printf("%lld", (answ - f[0][0] + mo) % mo);
return 0;
}