专栏文章

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

GGenius_Star影
P11893题解参与者 12已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@miqf479t
此快照首次捕获于
2025/12/04 03:46
3 个月前
此快照最后确认于
2025/12/04 03:46
3 个月前
查看原文
出题人题解。

思路：

动态规划做法（60pts）：

定义：
dp[i][1]→2dp[i][1] \to 2
dp[i][2]→3dp[i][2] \to 3
dp[i][3]→0,2dp[i][3] \to 0,2
dp[i][4]→0,3dp[i][4] \to 0,3
dp[i][5]→2,3dp[i][5] \to 2,3
dp[i][6]→3,4dp[i][6] \to 3,4
dp[i][7]→0,1,2dp[i][7] \to 0,1,2
dp[i][8]→0,1,3dp[i][8] \to 0,1,3
dp[i][9]→0,2,3dp[i][9] \to 0,2,3
dp[i][10]→0,3,4dp[i][10] \to 0,3,4
dp[i][11]→2,3,4dp[i][11] \to 2,3,4
dp[i][12]→0,1,2,3dp[i][12] \to 0,1,2,3
dp[i][13]→0,1,3,4dp[i][13] \to 0,1,3,4
dp[i][14]→0,2,3,4dp[i][14] \to 0,2,3,4
dp[i][15]→0,1,2,3,4dp[i][15] \to 0,1,2,3,4
以上表示 ii 位数中仅用了后面的数且满足题目要求的数的个数。
则状态转移方程为：
dp[i][1]=dp[i][2]=1dp[i][1]=dp[i][2]=1
dp[i][3]=dp[i−1][1]+dp[i−1][3]×2dp[i][3]=dp[i-1][1]+dp[i-1][3] \times 2
dp[i][4]=dp[i−1][2]+dp[i−1][4]×2dp[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]×2dp[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][6]=dp[i-1][2]+dp[i-1][6]
dp[i][7]=dp[i−1][3]+dp[i−1][7]×2dp[i][7]=dp[i-1][3]+dp[i-1][7] \times 2
dp[i][8]=dp[i−1][4]+dp[i−1][8]×2dp[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]×3dp[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]×2dp[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]×2dp[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]×3dp[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]×2dp[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]×3dp[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]×3dp[i][15]=dp[i-1][12]+dp[i-1][13]+dp[i-1][14]+dp[i-1][15] \times 3
答案为：dp[n][15]dp[n][15]。
时间复杂度为 O(N)O(N)，可以得到 3030 分。
之后考虑矩阵快速幂：
经过计算得 basebase 为：
∣111010000000000000111000000000002000101000000000200011100000000020001010000000001000110000000000200001000000000020001100000000003001010000000000200110000000000020010000000000003001000000000000201000000000000031000000000000003∣\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}
之后按照初始矩阵 AA（除了 (1,1)(1, 1) 和 (1,2)(1, 2) 处为 11，其他都为 00），进行快速幂即可。
时间复杂度为 O(log⁡N×W3),W=15O(\log N \times W^3), W = 15，可以获得 60pts。

组合数学做法（100pts）

考虑设序列 A={00⋯0011⋯11}A = \{00\cdots0011\cdots11\} 的长度为 xx，序列 B={33⋯3344⋯44}B = \{33\cdots3344\cdots44\} 的长度为 yy，则相当于将这两个序列插入到这 nn 个位置中。
容易知道，若 AA 的长度为 xx，则可能的 AA 有 (x−1)(x - 1) 个，BB 同理。
且由于首位不能为 00，则相当于在后面的 n−1n - 1 选 xx 个放 AA，然后在剩下的 n−xn - x 个位置放 BB，没放的显然是填 22，那么答案为：
Ans=∑x=2n−1∑y=2n−x−1(n−1x)(x−1)(n−xy)(y−1)=∑x=2n−2(n−1x)(x−1)(∑y=0n−x(n−xy)(y−1)−n+x+2)=∑x=2n−2(n−1x)(x−1)(∑y=0n−x(n−xy)y−2n−x−n+x+2)=∑x=2n−1(n−1x)(x−1)((n−x)∑y=0n−x(n−x−1y−1)−2n−x−n+x+2)=∑x=2n−1(n−1x)(x−1)((n−x)2n−x−1−2n−x−n+x+2)=∑x=0n−1(n−1x)(x−1)((n−x)2n−x−1−2n−x−n+x+2)+(n2n−1−2n−n+2)=∑x=0n−1(n−1x)x((n−x)2n−x−1−2n−x−n+x+2)−∑x=0n−1(n−1x)((n−x)2n−x−1−2n−x−n+x+2)+(n2n−1−2n−n+2)=(n−1)∑x=0n−2(n−2x)((n−x−1)2n−x−2−2n−x−1−n+x+3)−∑x=0n−1(n−1x)(n−x)2n−x−1+∑x=0n−1(n−1x)2n−x+n2n−1−(n−1)2n−2−2n+n2n−1−2n−n+2=(n−1)∑x=0n−2(n−2x)((n−x−1)2n−x−2−2n−x−1−n+x+3)−∑x=0n−1(n−1x)(n−x)2n−x−1+∑x=0n−1(n−1x)2n−x+(3n−7)2n−2−n+2=(n−1)∑x=0n−2(n−2x)((n−x−1)2n−x−2−2n−x−1−n+x+3)−n∑x=0n−1(n−1x)2n−x−1+∑x=0n−1(n−1x)x2n−x−1+2×3n−1+(3n−7)2n−2−n+2=(n−1)∑x=0n−2(n−2x)((n−x−1)2n−x−2−2n−x−1−n+x+3)+(n−1)∑x=0n−2(n−2x)2n−x−2−n3n−1+2×3n−1+(3n−7)2n−2−n+2=(n−1)∑x=0n−2(n−2x)((n−x−1)2n−x−2−2n−x−1−n+x+3)−(2n−5)3n−2+(3n−7)2n−2−n+2=(n−1)(∑x=0n−2(n−2x)(n−x−1)2n−x−2−∑x=0n−2(n−2x)2n−x−1−n∑x=0n−2(n−2x)+∑x=0n−2(n−2x)x+3∑x=0n−2(n−2x))−(2n−5)3n−2+(3n−7)2n−2−n+2=(n−1)((n−1)∑x=0n−2(n−2x)2n−x−2−∑x=0n−2(n−2x)x2n−x−2−2×3n−2−n2n−2+(n−2)2n−3+3×2n−2)−(2n−5)3n−2+(3n−7)2n−2−n+2=(n−1)((n−1)3n−2−(n−2)3n−3−2×3n−2−n2n−2+(n−2)2n−3+3×2n−2)−(2n−5)3n−2+(3n−7)2n−2−n+2=−5 n 3n−2−9 2n−2+2 n2 3n−3+22 3n−3−n2 2n−3+11 n 2n−3−n+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}
上面的推理运用了以下恒等式：
  • ∑i=0n(ni)=2n\sum_{i = 0}^n \binom{n}{i} = 2^n
证明： 考虑组合意义，在 nn 个物品中选任意个，每个物品选或不选，方案数是 2n2^n。
  • (nm)m=n(n−1m−1)\binom{n}{m}m = n \binom{n - 1}{m - 1}
证明： (nm)m=n!m!(n−m)!m=n!(m−1)(n−m)!=n(n−1)!(m−1)!(n−m)!=n(n−1m−1)\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=0n(ni)2n−i=3n\sum_{i = 0}^n \binom{n}{i} 2^{n - i} = 3^n
证明： 考虑组合意义，每个物品有三种形态，枚举仅有 ii 个物品是第一种形态，则剩下的 n−in - i 个物品在剩下两种形态任选；等价于所有形态的方案数 3n3^n。
时间复杂度为 O(len+log⁡mod)O(len + \log mod)。
主要考察选手组合数学基本功。
CPP
#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;
}

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...