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

· · 题解

出题人题解。

思路：

动态规划做法（60pts）：

定义：

dp[i][1] \to 2 dp[i][2] \to 3 dp[i][3] \to 0,2 dp[i][4] \to 0,3 dp[i][5] \to 2,3 dp[i][6] \to 3,4 dp[i][7] \to 0,1,2 dp[i][8] \to 0,1,3 dp[i][9] \to 0,2,3 dp[i][10] \to 0,3,4 dp[i][11] \to 2,3,4 dp[i][12] \to 0,1,2,3 dp[i][13] \to 0,1,3,4 dp[i][14] \to 0,2,3,4 dp[i][15] \to 0,1,2,3,4

以上表示 i 位数中仅用了后面的数且满足题目要求的数的个数。

则状态转移方程为：

dp[i][1]=dp[i][2]=1 dp[i][3]=dp[i-1][1]+dp[i-1][3] \times 2 dp[i][4]=dp[i-1][2]+dp[i-1][4] \times 2 dp[i][5]=dp[i-1][1]+dp[i-1][2]+dp[i-1][5] \times 2 dp[i][6]=dp[i-1][2]+dp[i-1][6] dp[i][7]=dp[i-1][3]+dp[i-1][7] \times 2 dp[i][8]=dp[i-1][4]+dp[i-1][8] \times 2 dp[i][9]=dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][9] \times 3 dp[i][10]=dp[i-1][4]+dp[i-1][6]+dp[i-1][10] \times 2 dp[i][11]=dp[i-1][5]+dp[i-1][6]+dp[i-1][11] \times 2 dp[i][12]=dp[i-1][7]+dp[i-1][8]+dp[i-1][9]+dp[i-1][12] \times 3 dp[i][13]=dp[i-1][8]+dp[i-1][10]+dp[i-1][13] \times 2 dp[i][14]=dp[i-1][9]+dp[i-1][10]+dp[i-1][11]+dp[i-1][14] \times 3 dp[i][15]=dp[i-1][12]+dp[i-1][13]+dp[i-1][14]+dp[i-1][15] \times 3

答案为：dp[n][15]。

时间复杂度为 O(N)，可以得到 30 分。

之后考虑矩阵快速幂：

经过计算得 base 为：

\begin{vmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \end{vmatrix}

之后按照初始矩阵 A（除了 (1, 1) 和 (1, 2) 处为 1，其他都为 0），进行快速幂即可。

时间复杂度为 O(\log N \times W^3), W = 15，可以获得 60pts。

组合数学做法（100pts）

考虑设序列 A = \{00\cdots0011\cdots11\} 的长度为 x，序列 B = \{33\cdots3344\cdots44\} 的长度为 y，则相当于将这两个序列插入到这 n 个位置中。

容易知道，若 A 的长度为 x，则可能的 A 有 (x - 1) 个，B 同理。

且由于首位不能为 0，则相当于在后面的 n - 1 选 x 个放 A，然后在剩下的 n - x 个位置放 B，没放的显然是填 2，那么答案为：

\begin{aligned} Ans &= \sum_{x = 2}^{n - 1} \sum_{y = 2}^{n - x - 1} \binom{n - 1}{x} (x - 1) \binom{n - x}{y} (y - 1) \\ &= \sum_{x = 2}^{n - 2} \binom{n - 1}{x} (x - 1) \left( \sum_{y = 0}^{n - x} \binom{n - x}{y} (y -1) - n + x + 2\right) \\ &= \sum_{x = 2}^{n - 2} \binom{n - 1}{x} (x - 1) \left( \sum_{y = 0}^{n - x} \binom{n - x}{y} y -2^{n - x}-n + x + 2\right) \\ &= \sum_{x = 2}^{n - 1} \binom{n - 1}{x} (x - 1) \left((n - x)\sum_{y = 0}^{n - x}\binom{n - x - 1}{y - 1} - 2^{n - x} - n + x + 2\right) \\ &= \sum_{x = 2}^{n - 1} \binom{n - 1}{x}(x - 1)\left( (n - x) 2^{n - x - 1} - 2^{n - x} - n + x + 2\right) \\ &= \sum_{x = 0}^{n-1 }\binom{n - 1}{x}(x - 1)\left( (n - x) 2^{n - x - 1} - 2^{n - x} - n + x + 2\right) + \left(n2^{n - 1} - 2^n - n + 2\right) \\ &= \sum_{x = 0}^{n - 1} \binom{n - 1}{x} x \left( (n - x) 2^{n - x - 1} - 2^{n - x} - n + x + 2\right) \\ &-\sum_{x = 0}^{n - 1} \binom{n - 1}{x} \left( (n - x) 2^{n - x - 1} - 2^{n - x} - n + x + 2\right) \\ &+\left(n2^{n - 1} - 2^n - n + 2\right) \\ &= (n - 1) \sum_{x = 0}^{n - 2} \binom{n - 2}{x} \left( (n - x - 1) 2^{n - x - 2} - 2^{n - x - 1} - n + x + 3\right) \\ &-\sum_{x = 0}^{n - 1} \binom{n - 1}{x} (n - x) 2^{n - x - 1}+ \sum_{x = 0}^{n - 1} \binom{n - 1}{x} 2^{n - x} \\& + n 2^{n - 1} - (n - 1)2^{n - 2} - 2^n + n2^{n - 1} - 2^n - n + 2 \\ &= (n - 1) \sum_{x = 0}^{n - 2} \binom{n - 2}{x} \left( (n - x - 1) 2^{n - x - 2} - 2^{n - x - 1} - n + x + 3\right) \\ &-\sum_{x = 0}^{n - 1} \binom{n - 1}{x} (n - x) 2^{n - x - 1}+ \sum_{x = 0}^{n - 1} \binom{n - 1}{x} 2^{n - x} \\ &+ (3n - 7) 2^{n - 2} - n + 2 \\&= (n - 1) \sum_{x = 0}^{n - 2} \binom{n - 2}{x} \left( (n - x - 1) 2^{n - x - 2} - 2^{n - x - 1} - n + x + 3\right) \\ &-n\sum_{x = 0}^{n - 1} \binom{n - 1}{x} 2^{n - x - 1} + \sum_{x = 0}^{n - 1} \binom{n - 1}{x} x 2^{n - x - 1} \\&+ 2 \times 3^{n - 1} + (3n - 7) 2^{n - 2} - n + 2 \\ &=(n - 1) \sum_{x = 0}^{n - 2} \binom{n - 2}{x} \left( (n - x - 1) 2^{n - x - 2} - 2^{n - x - 1} - n + x + 3\right) \\ &+(n - 1)\sum_{x = 0}^{n - 2} \binom{n - 2}{x} 2^{n - x - 2} \\&-n 3^{n - 1}+ 2 \times 3^{n - 1} + (3n - 7) 2^{n - 2} - n + 2 \\ &= (n - 1) \sum_{x = 0}^{n - 2} \binom{n - 2}{x} \left( (n - x - 1) 2^{n - x - 2} - 2^{n - x - 1} - n + x + 3\right) \\ &-(2n - 5)3^{n - 2} + (3n - 7) 2^{n - 2} - n + 2 \\ &= (n - 1) \Big(\sum_{x = 0}^{n - 2} \binom{n - 2}{x} (n - x - 1)2^{n - x - 2} - \sum_{x = 0}^{n - 2} \binom{n - 2}{x}2^{n - x - 1} \\ &- n \sum_{x = 0}^{n - 2} \binom{n - 2}{x} + \sum_{x = 0}^{n - 2} \binom{n - 2}{x} x + 3 \sum_{x = 0}^{n - 2} \binom{n - 2}{x} \Big) \\ &-(2n - 5)3^{n - 2} + (3n - 7) 2^{n - 2} - n + 2 \\ &= (n - 1)\Big((n - 1) \sum_{x = 0}^{n - 2} \binom{n - 2}{x} 2^{n - x - 2} - \sum_{x = 0}^{n - 2} \binom{n - 2}{x} x 2^{n - x - 2} \\ &- 2 \times 3^{n - 2}- n 2^{n - 2} + (n - 2)2^{n - 3} + 3 \times 2^{n - 2} \Big) \\ &-(2n - 5)3^{n - 2} + (3n - 7) 2^{n - 2} - n + 2 \\ &= (n - 1) \left((n - 1) 3^{n - 2} - (n - 2)3^{n - 3} - 2 \times 3^{n - 2} - n 2^{n - 2} + (n - 2)2^{n - 3} + 3 \times 2^{n - 2} \right) \\ &-(2n - 5)3^{n - 2} + (3n - 7) 2^{n - 2} - n + 2 \\ &= -5\,n\,3^{n-2}-9\,2^{n-2}+2\,n^2\,3^{n-3}+22\,3^{n-3}-n^2\,2^{n-3}+ 11\,n\,2^{n-3}-n+2 \end{aligned}

上面的推理运用了以下恒等式：

证明： 考虑组合意义，在 n 个物品中选任意个，每个物品选或不选，方案数是 2^n。

证明：

\begin{aligned} \binom{n}{m}m &= \frac{n!}{m!(n - m)!}m \\&= \frac{n!}{(m - 1)(n - m)!} \\&= n \frac{(n - 1)!}{(m - 1)!(n - m)!} \\&=n \binom{n - 1}{m - 1} \end{aligned}

证明： 考虑组合意义，每个物品有三种形态，枚举仅有 i 个物品是第一种形态，则剩下的 n - i 个物品在剩下两种形态任选；等价于所有形态的方案数 3^n。

时间复杂度为 O(len + \log mod)。

主要考察选手组合数学基本功。

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define int long long
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e7 + 10, mod = 1e9 + 7; 
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, mn, mbase = 1, len, sum, base = 1;
char s[N];
inline int qpow(int a, int b){
    if(b < 0)
      b += mod - 1;
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
bool End;
signed main(){
    len = read();
    scanf("%s", s + 1);
    for(int i = len; i >= 1; --i){
        n += (s[i] - '0') * base;
        mn += (s[i] - '0') * mbase;
        n %= mod;
        mn %= (mod - 1);
        base = base * 10ll % mod;
        mbase = mbase * 10ll % (mod - 1);
    }
    sum = (mod - 5ll * n % mod * qpow(3, mn - 2) % mod) + (mod - 9ll * qpow(2, mn - 2) % mod) + 2ll * n % mod * n % mod * qpow(3, mn - 3) % mod + 22ll * qpow(3, mn - 3) % mod + (mod - n * n % mod * qpow(2, mn - 3) % mod) + 11ll * n % mod * qpow(2, mn - 3) % mod + (mod - n) + 2;
    write(sum % mod);
    cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}