题解 P5363 【[SDOI2019]移动金币】

· · 题解

首先我们会发现最后一枚棋子的移动是与别的棋子有所不同的，移动别的棋子的时候，并没有改变走向最终结束状态的步数，相当于是把它后面一段空格内的一些格子“移动”到了上一段空格内。而如果走最后一个，就相当于把后面一段空格里的格子扔掉了。

咦，这不阶梯博弈吗？

那么我们现在的问题就转化为了，我们要用m个棋子把n个格子划分为可空的m+1段，或者换句话说，把n-m个格子装入m+1个盒子，使得从左开始数第偶数个（因为最右边还有一段空的）盒子的异或和为0（拿总数减去就是答案了）。

这个看起来十分的不可做，但是我们想，异或为0即对于每一位，这一位是1的个数有偶数个。所以，我们可以考虑每个盒子的棋子个数二进制拆分成若干个不同的2^k之和，那么我们就按位考虑每一位，对于每一位k我们会往偶数个偶盒子里每一个都放2^k个格子。

那么就可以dp了，dp[i][j]表示放完前i位，还剩j个格子没放，那么就有dp[i][j]=\sum_{k\%2=0}dp[i+1][j-2^ik]C_{q}^k，其中q=\lfloor\frac{m+1}2\rfloor即偶盒子的个数。

那么我们最终把剩下的格子用插板法放到奇盒子里即可。O(nm\log n)。跑得比我想象的快多了

上代码~

#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);
}