P15073 [ICPC 2024 Chengdu R] Athlete Welcome Ceremony
题目描述
成都即将举办 2025 年世界运动会。在开幕式运动员欢迎仪式上，将有
n
n
n 名志愿者穿着三种不同类型的传统民俗服装，列队欢迎运动员。这些服装类型用
a
\\texttt{a}
a、
b
\\texttt{b}
b 和
c
\\texttt{c}
c 表示。志愿者的位置已经确定，现在我们需要为他们分配服装。为了实现特定的视觉效果，相邻的志愿者不能穿着相同类型的服装。
在这
n
n
n 名志愿者中，一些人已经拥有三种民俗服装中的一种，而另一些人则没有任何服装，需要主办方提供定制服装。共有
Q
Q
Q 个定制计划，每个计划指定：制作
x
x
x 套
a
\\texttt{a}
a 型服装、
y
y
y 套
b
\\texttt{b}
b 型服装和
z
z
z 套
c
\\texttt{c}
c 型服装。
对于每个定制计划，确定在将定制服装分发给没有服装的志愿者后，可以形成多少种不同的有效服装安排。具体来说，在不超过给定计划限制的条件下，计算分配
a
\\texttt{a}
a、
b
\\texttt{b}
b 和
c
\\texttt{c}
c 型服装的方案数。如果两种安排中同一名志愿者分配的服装类型不同，则视为不同的安排。注意，同一类型的服装彼此不作区分。由于数量可能非常大，请输出答案对
10
9
+
7
10^9+7
109+7 取模的结果。
输入格式
- 第一行包含两个整数
n
n
n（1
≤
n
≤
300
1\\le n\\le 300
1≤n≤300）和Q
Q
Q（1
≤
Q
≤
10
5
1\\le Q\\le 10^5
1≤Q≤105），分别表示志愿者人数和定制计划的数量。 - 第二行是一个长度为
n
n
n 的字符串s
s
s。保证字符串s
s
s 仅包含字符a
\\texttt{a}
a、b
\\texttt{b}
b、c
\\texttt{c}
c 和?
\\texttt{?}
?。如果第i
i
i 个字符是a
\\texttt{a}
a、b
\\texttt{b}
b、c
\\texttt{c}
c 之一，则表示第i
i
i 名志愿者已经拥有对应的服装；否则，如果是?
\\texttt{?}
?，则表示第i
i
i 名志愿者没有任何服装。 - 接下来的
Q
Q
Q 行，每行包含三个整数x
,
y
,
z
x, y, z
x,y,z（0
≤
x
,
y
,
z
≤
300
0 \\le x, y, z \\le 300
0≤x,y,z≤300），表示一个定制计划。保证x
+
y
+
z
x+y+z
x+y+z 不小于没有服装的志愿者人数。
输出格式
输出
Q
Q
Q 行，第
i
i
i 行包含一个整数，表示满足第
i
i
i 个定制计划要求的有效服装安排数量。请输出答案对
10
9
+
7
10^9+7
109+7 取模的结果。
输入输出样例 #1
输入 #1
6 3
a?b??c
2 2 2
1 1 1
1 0 2
输出 #1
3
1
1
输入输出样例 #2
输入 #2
6 3
??????
2 2 2
2 3 3
3 3 3
输出 #2
30
72
96
说明/提示
在第一个样例中，第一个定制计划的有效服装安排是
acbabc
\\texttt{acbabc}
acbabc、
acbcac
\\texttt{acbcac}
acbcac 和
acbcbc
\\texttt{acbcbc}
acbcbc。
翻译由 DeepSeek V3 完成
思路
考虑DP,
f
i
,
j
,
k
,
l
f_{i,j,k,l}
fi,j,k,l表示到i，a选j个，b选k个，当前点为l。 转移则容易。 然后做个后缀和，讨论范围即可。
代码见下
#include<bits/stdc++.h>
using namespace std;
long long n,q,a[305],f[305][305][305][4],g[305][305],m=0,x,y,z,op=0;
char ch;
const long long mod=1e9+7;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>ch;
if(ch=='a'){
a[i]=1;
}
else if(ch=='b'){
a[i]=2;
}
else if(ch=='c'){
a[i]=3;
}
else{
a[i]=0;
m++;
}
}
f[0][0][0][0]=1;
for(int i=1;i<=n;i++){
if(a[i]!=0){
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){
for(int l=0;l<=3;l++){
if(a[i]!=l){
f[i][j][k][a[i]]=(f[i][j][k][a[i]]+f[i–1][j][k][l])%mod;
}
}
}
}
}
else{
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){
if(j>=1){
f[i][j][k][1]=(f[i][j][k][1]+f[i–1][j–1][k][0])%mod;
f[i][j][k][1]=(f[i][j][k][1]+f[i–1][j–1][k][2])%mod;
f[i][j][k][1]=(f[i][j][k][1]+f[i–1][j–1][k][3])%mod;
}
if(k>=1){
f[i][j][k][2]=(f[i][j][k][2]+f[i–1][j][k–1][0])%mod;
f[i][j][k][2]=(f[i][j][k][2]+f[i–1][j][k–1][1])%mod;
f[i][j][k][2]=(f[i][j][k][2]+f[i–1][j][k–1][3])%mod;
}
f[i][j][k][3]=(f[i][j][k][3]+f[i–1][j][k][0])%mod;
f[i][j][k][3]=(f[i][j][k][3]+f[i–1][j][k][1])%mod;
f[i][j][k][3]=(f[i][j][k][3]+f[i–1][j][k][2])%mod;
}
}
}
// for(int j=0;j<=m;j++){
// for(int k=0;k<=m;k++){
// for(int l=0;l<=3;l++){
// cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<f[i][j][k][l]<<endl;
// }
// }
// }
}
for(int i=0;i<=m;i++){
for(int j=0;j<=m;j++){
for(int l=0;l<=3;l++){
g[i][j]=(g[i][j]+f[n][i][j][l])%mod;
}
//cout<<i<<" "<<j<<" "<<g[i][j]<<endl;
if(j!=0){
g[i][j]=(g[i][j]+g[i][j–1])%mod;
}
}
}
while(q—){
cin>>x>>y>>z;
x=min(x,m);
y=min(y,m);
z=min(z,m);
op=0;
for(int i=0;i<=x;i++){
if(m–i–z<=y){
if(m–i–z–1>=0){
op=(op+g[i][y]–g[i][m–i–z–1]+mod)%mod;
}
else{
op=(op+g[i][y])%mod;
}
}
}
cout<<op<<"\\n";
}
return 0;
}
