题解：P11893 [XRCOI Round 1] D. 似此星辰非昨夜

· · 题解

赛时没时间口胡的。赛后已复现。

首先考虑 n 位数中选出 i 个是 0 或 1，j 个是 3 或 4，其余填 2。这样答案就是：

\sum_{i=2}^{n-1}\sum_{j=2}^{n-i-1}{{n-1}\choose{i}}{{n-i-1}\choose{j}}(i-1)(j-1)

分离并作简单的计算得到：

\sum_{i=2}^{n-1}{{n-1}\choose{i}}(i-1)\left(\sum_{j=2}^{n-i-1}\left((n-i-1){{n-i-2}\choose{j-1}}-{{n-i-1}\choose{j}}\right)\right)

进一步得到：

\sum_{i=2}^{n-1}{{n-1}\choose{i}}(i-1)\left((n-i-1)2^{n-i-2}-2^{n-i-1}+1\right)

即：

\sum_{i=2}^{n-1}\left((n-1){{n-2}\choose{i-1}}-{{n-1}\choose{i}}\right)\left((n-i-1)2^{n-i-2}-2^{n-i-1}+1\right)

然后我们如法炮制把上面的东西进一步拆开：

(2n^2-15n+22)3^{n-3}-(n^2-11n+18)2^{n-3}-n+2

就可以强行算了。常数极小。

当然如果你注意力惊人会知道算到这个地方的时候答案一定会是常数的幂乘以多项式，直接待定系数即可。

#include <bits/stdc++.h>
using namespace std;

struct FastIO {
    inline FastIO& operator >> (short& x) {
        x = 0;
        char f = 0, ch = getchar();
        while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (int& x) {
        x = 0;
        char f = 0, ch = getchar();
        while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (long long& x) {
        x = 0;
        char f = 0, ch = getchar();
        while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while (ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (double& x) {
        x = 0;
        char f = 0, ch = getchar();
        double d = 0.1;
        while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while (ch <= '9' && ch >= '0') x = x * 10 + (ch ^ 48), ch = getchar();
        if (ch == '.') {
            ch = getchar();
            while (ch <= '9' && ch >= '0') x += d * (ch ^ 48), d *= 0.1, ch = getchar();
        }
        return x = (f ? -x : x), *this;
    }
} rin;

#define ll long long
#define uint unsigned int
#define reg register
#define ld long double
#define uint unsigned int
#define ull unsigned long long
#define qint const int&
#define qll const ll&
#define quint cosnt uint&
#define qull const ull&
#define endl "\n"

inline void qmod(int& x, const int& mod) {
    x = x >= mod? x - mod : x;
}

const int N = 1e7 + 10, mod = 1e9 + 7, Mod = mod - 1;
int l;
ll val, idx;
char ch[N];
inline int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

signed main() {
    rin >> l, cin >> ch;
    if (l <= 1 && ch[0] <= '4') return puts("0"), 0;
    for (int i = 0; i < l; ++i) {
        val = ((val << 3) + (val << 1) + (ch[i] ^ 48)) % mod;
        idx = ((idx << 3) + (idx << 1) + (ch[i] ^ 48)) % Mod;
    }
    ll res = (2 * val * val - 15 * val + 22) % mod * qpow(3, idx - 3) % mod;
    res -= (val * val - 11 * val + 18) % mod * qpow(2, idx - 3) % mod;
    res = res - val + 2;
    res = (res % mod + mod) % mod;
    cout << res << endl;
    return 0;
}

拜谢 @Ruan_ji 提出的错误。