Editorial for Dãy đèn (OLP MT&TN 2022 CT)
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1:
Với subtask \(1\) (\(n, t \leq 6\)), ta có thể sử dụng quay lui.
Subtask 2:
Gọi \(dp(i, x, y)\) là số cách tạo thành dãy có \(x\) đèn ở trạng thái xanh và \(y\) đèn ở trạng thái đỏ khi sử dụng \(i\) thao tác
res=0;
- Ta có thể dùng \(1\) thao tác để chuyển trạng thái không màu thành trạng thái màu xanh;
res+=dp(i+1, x+1, y)*(n-x-y);
- Nếu \(x \geq 1\), ta có thể dùng \(1\) thao tác để chuyển thành trạng thái màu đỏ;
res+=dp(i+1, x-1, y+1)*x;
- Nếu \(y \geq 0\), ta có thể dùng \(1\) thao tác để chuyển thành trạng thái không màu.
res+=dp(i+1, x, y-1)*y;
Reference Code:
C++
const int mod=1e9+7, limit=605;
int n, t, a, b, d[limit][limit][limit], l[limit][limit][limit];
int dp(int i, int x, int y){
if(d[i][x][y]==1) return l[i][x][y];
if(i==t){
return (x==a&&y==b);
}
long long res=dp(i+1, x+1, y), temp;
res=(res*(n-x-y))%mod;
if(x>=1){
temp=dp(i+1, x-1, y+1);
temp=(temp*x)%mod;
res=(res+temp)%mod;
}
if(y>=1){
temp=dp(i+1, x, y-1);
temp=(temp*y)%mod;
res=(res+temp)%mod;
}
d[i][x][y]=1;
l[i][x][y]=res;
return res;
}
int main(){
cin >> n >> t >> a >> b;
cout << dp(0, 0, 0);
}
Subtask 3:
Nhận xét:
- Nếu để mảng \(f[605][605][605]\) thì nó sẽ bị \(RTE\);
- Chúng ta chỉ quan tâm tới thao tác trước và thao tác sau, nên để không bị \(RTE\) ta có thế để mảng \(f[2][605][605]\) để xử lí.
Nếu xử lí như trên thì ta phải dp bằng \(for\)
Time: \(O(605^{3})\)
C++
const int mod=1e9+7;
int n, t, a, b;
long long f[2][605][605];
int main(){
cin >> n >> t >> a >> b;
f[0][0][0]=1;
for(int i=0; i<t; i++){
int u=i%2, v=(i+1)%2;
for(int x=0; x<=n; x++){
for(int y=0; y<=n-x; y++){
f[v][x][y]=0;
}
}
for(int x=0; x<=n; x++){
for(int y=0; y<=n-x; y++){
f[v][x+1][y]=(f[v][x+1][y]+f[u][x][y]*(n-x-y))%mod;
if(x>0) f[v][x-1][y+1]=(f[v][x-1][y+1]+f[u][x][y]*x)%mod;
if(y>0) f[v][x][y-1]=(f[v][x][y-1]+f[u][x][y]*y)%mod;
}
}
}
cout << f[t%2][a][b];
}
Comments