考场的时候没什么时间来想这道题。。。
通过打表找规律（题解），可以发现当(n)为奇数的时候先手必胜。
而对于(n)为偶数的情况。观察当前排列的方案数。
可以证明当当前排列的方案数为偶数的时候，先手必胜。
证明：若删字符可胜，便删字符；否则便重排，最后必定是后手不得不删字符（无法再重排）。
而对于方案数为奇数的情况的话，则可以证明删字符后的排列方案数仍为奇数，所以后手必胜。
综上，(n)为偶数时当前排列方案数为偶数的话先手才必胜，否则后手必胜。
考虑计算当前排列方案数为奇数的个数，观察(2)的个数。
显然，对于 (n!)，质因数分解中(2)的次数为(sum_i leftlfloordfrac{n}{2^i}
ight
floor)。
若排列有奇数种，则对任意(x)有：(sum_{i=1}^kleftlfloordfrac{a_i}{2^x} ight floor=leftlfloordfrac{n}{2^x} ight floor)
也就是对于二进制的每一位，要满足(sum a[i]_k = n_k)。
于是我们可以用(DP)求解，设(f[i][j])表示当前用第(i)种字符，而当前(sum a[i])为(j)的时候的方案数。
可以得到显然的转移：(f[i][j]=sum f[i - 1][l] / (j - l)!)，其中(l)是(j)的一个二进制子集。
由于求的是奇数中排列的方案数，答案便为(k^n-f[K][n]*n!)。当这样转移时间复杂度过高，会(TLE)。
(force code)
#include <cstdio>
#define N 250010
#define mo 1000000009
#define ll long long
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
using namespace std;
int n, K;
ll jc[N], ny[N], f[27][N], ans = 1;
ll ksm(ll x, int y) {
ll s = 1;
while (y) {
if (y & 1) s = s * x % mo;
x = x * x % mo, y >>= 1;
}
return s;
}
void prepare() {
jc[0] = ny[0] = 1;
fo(i, 1, n) jc[i] = jc[i - 1] * i % mo;
ny[n] = ksm(jc[n], mo - 2);
fd(i, n - 1, 1) ny[i] = ny[i + 1] * (i + 1) % mo;
}
int main()
{
freopen("onmyodo.in", "r", stdin);
freopen("onmyodo.out", "w", stdout);
scanf("%d%d", &n, &K);
prepare(); ans = ksm(K, n);
if (n & 1) return 0 & printf("%lld
", ans);
f[0][0] = 1;
fo(i, 1, K) fo(j, 0, n) {
f[i][j] = f[i - 1][0] * ny[j] % mo;
for (int k = j; k; k = (j & (k - 1)))
f[i][j] = (f[i][j] + f[i - 1][k] * ny[j - k]) % mo;
}
printf("%lld
", (ans - jc[n] * f[K][n] % mo + mo) % mo);
return 0;
}
所以我们要考虑优化一下(DP)。
考虑转移的时候下一种字符强制包含剩下的(n')中的(1)的最低位。
这样我们的(i)就变成了用了(i)种字符了，而对于下一种字符是哪一个，并没有什么强制要求。
最后的奇数种排列的方案数就变成了(sum f[i][n]*k!/(k-i)!)。
#include <cstdio>
#define N 250010
#define mo 1000000009
#define ll long long
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
using namespace std;
int n, K;
ll jc[N], ny[N], f[27][N], ans = 1, sum;
ll ksm(ll x, int y) {
ll s = 1;
while (y) {
if (y & 1) s = s * x % mo;
x = x * x % mo, y >>= 1;
}
return s;
}
void prepare(int tot) {
jc[0] = ny[0] = 1;
fo(i, 1, tot) jc[i] = jc[i - 1] * i % mo;
ny[tot] = ksm(jc[tot], mo - 2);
fd(i, tot - 1, 1) ny[i] = ny[i + 1] * (i + 1) % mo;
}
bool check(int x, int y) {
if ((x & y) != y) return 1;
int s = 1, mx = 0;
while (x) {
if (x & 1) mx = s;
s <<= 1, x >>= 1;
}
if (mx != y) return 1;
return 0;
}
int main()
{
freopen("onmyodo.in", "r", stdin);
freopen("onmyodo.out", "w", stdout);
scanf("%d%d", &n, &K);
prepare(n > K ? n : K); ans = ksm(K, n);
if (n & 1) return 0 & printf("%lld
", ans);
f[0][0] = 1;
fo(i, 0, K - 1) fo(j, 0, n - 1) {
if (! f[i][j] || (j & n) != j) continue;
int rem = n ^ j, nx = rem & (-rem); rem = rem ^ nx;
f[i + 1][j | nx] = (f[i + 1][j | nx] + f[i][j] * ny[nx]) % mo;
for (int k = rem; k; k = (rem & (k - 1)))
f[i + 1][j | k | nx] = (f[i + 1][j | k | nx] + f[i][j] * ny[k | nx]) % mo;
}
fo(i, 1, K) sum = (sum + f[i][n] * jc[K] % mo * ny[K - i] % mo) % mo;
printf("%lld
", (ans - jc[n] * sum % mo + mo) % mo);
return 0;
}