专栏文章

NOIP rp++！|| solution - AT_abc433_f

llittlebug
AT_abc433_f题解参与者 5已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@min29kxx
此快照首次捕获于
2025/12/01 19:23
3 个月前
此快照最后确认于
2025/12/01 19:23
3 个月前
查看原文
OI 生涯最后一场 abc 了。写篇题解留下个纪念吧。
作为一个非常不会数数题的人，罕见的场切了数数题，保佑我 NOIP 也有这样的运气吧。
首先因为每个情况都可以表示为一段 ii 拼上一段 i+1i+1 的形式，所以只讨论 i=1i=1 的情况，其它情况都是同理的。
枚举中间的那个 11，考虑这个 11 右边的每个 22。分别统计这个 11 左边 11 的个数、这个 22 右边 22 的个数，可以得到得到这样的序列：
11…1⏟x个1222…2⏟y个\underbrace{11 \ldots 1} _{x \text{个}} 1 2 \underbrace{22 \ldots 2} _{y \text{个}}
那么考虑最左边的 22（即和 11 相邻的那个 22）可能是哪个，以及选几个数（这样可以保证不重不漏），可以得到式子：
∑i=0y∑j=0min⁡(i,x)(xj)(ij)=∑i=0y∑j=0x(xj)(ij)=∑i=0y∑j=0x(xx−j)(ij)=∑i=0y(x+ix)=(x+y+1x+1)\begin{aligned} & \sum _{i=0} ^y \sum _{j=0} ^{\min(i,x)} \binom x j \binom i j \\ = & \sum _{i=0} ^y \sum _{j=0} ^x \binom x j \binom i j \\ = & \sum _{i=0} ^y \sum _{j=0} ^x \binom x {x-j} \binom i j \\ = & \sum _{i=0} ^y \binom {x+i} x \\ = & \binom {x+y+1} {x+1} \end{aligned}
第一步是因为 j>ij>i 的部分 (ij)=0\binom i j = 0，所以 min⁡\min 可以直接丢掉不管；第二步没什么好说的；第三步是范德蒙德恒等式；第四步是【我不知道叫什么】恒等式。
可以参考组合数学常用的基础恒等式。
时间复杂度 O(n∣Σ∣)O(n|\Sigma|)，其中 ∣Σ∣|\Sigma| 为字符集大小，在本题中为 1010。精细实现可以做到 O(n)O(n) 不过我懒。
代码：
CPP
// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,nxt[N][10],cnt[N][10];
string s;

il void solve(int __Ti)
{
	read(s),n=s.size(),s="$"+s+"###";
	
	rep(j,0,9) nxt[n+1][j]=n+1;
	rpe(i,n,1) rep(j,0,9) nxt[i][j]=s[i+1]-'0'==j?i+1:nxt[i+1][j],cnt[i][j]=cnt[i+1][j]+(s[i]-'0'==j);
	
	int ans=0,x,y;
	rep(i,1,n) if(s[i]<'9')
	{
		x=cnt[1][s[i]-'0']-cnt[i][s[i]-'0'];
		y=cnt[nxt[i][s[i]-'0'+1]][s[i]-'0'+1]-1;
		if(y<0) continue;
		add(ans,C(x+y+1,x+1));
	}
	
	write(ans);
}
华风夏韵，洛水天依！
NOIP rp++！

评论

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

正在加载评论...