8月22日模拟赛 T0 小W的玻璃弹珠 题解

爹级思维题。为什么是 T0 啊 nmd

题意简述

给出一个栈，你需要向其中按顺序投入 个弹珠，弹珠有 种不同颜色，你可以投入任意颜色的弹珠。如果栈顶部 颗弹珠颜色是相同的，你需要将它们取出。现在，要求求出能够使所有弹珠都被取出的投入方案数。

数据范围：。

思路分析

分析个头。分析不出来。直接讲做法。

考虑如果采用传统的方法，会发现状态与状态之间的重复极其难以处理。也就是说，我们应该按照放入的顺序逐个珠子进行考虑，这样就不需要管状态重复了。

自然想到设 代表前 颗珠子需要用 次消掉时的方案数。这里所谓的需要用多少次消掉，是说在整个投入珠子的过程当中，前 颗珠子参与到的消除有几次。也就是说，如果前 颗珠子不能够被消干净，那么剩余的珠子也需要参与计算消除次数。例如：122212221,l=3。在这个例子中，前 颗珠子就需要用 次来消除。因为中间的 可以直接一下消掉，两侧的 可以和后面的 一次消掉，所以一共是两次。

那么，我们考虑如何判断一个状态是否能够被完全消除。显然，这等价于 。那么对于一个状态，我们有一下两种情况：

1. 若 ，则意味着栈空，我们向栈中任意放入一个弹珠，都将转移到 ，因为这一颗新的弹珠一定要被消除一次。那么，我们直接 。

2. 若 ，则意味着栈非空，这意味着栈顶一定至少仍存在一颗弹珠，且目前栈顶的连续同色弹珠数量还不足以被消除。

   <1> 若新放入的弹珠与原本的栈顶颜色不同，那么这颗新的弹珠一定要被消除一次。也就是说，它一定无法和此前的同色弹珠被同一次消除，因为它们之间隔着异色的弹珠。又由于这颗新的弹珠有 种颜色可选，我们做 。

   <2> 若新放入的弹珠与原本的栈顶颜色相同，由于栈顶一定至少仍存在一颗弹珠，且目前栈顶的连续同色弹珠数量还不足以被消除，这颗新的弹珠一定可以跟栈顶弹珠同时被消除，即不需要多被消除一次。我们做 。

   注意：我们并不关心栈顶的颜色究竟是什么，我们只关心栈是否为空。在上述 2.<2> 情况中，有可能出现栈顶的弹珠变为可以被消去。此时，我们仍然能够根据 对栈空与否进行判断。可以理解为我们在不做任何操作的情况下将栈顶的弹珠消去了。

最终输出 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[4005][4005];//前i个需要消j次
signed main(){
	int l,n;
	cin>>l>>n;
	dp[1][1]=4;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(j*l==i) dp[i+1][j+1]=(1ll*dp[i+1][j+1]+1ll*dp[i][j]*4)%mod;
			else{
				dp[i+1][j+1]=(1ll*dp[i+1][j+1]+1ll*dp[i][j]*3)%mod;
				dp[i+1][j]=(1ll*dp[i+1][j]+1ll*dp[i][j])%mod;
			}
		}
	}
	cout<<dp[n][n/l];
	return 0;
}