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.

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

There are no comments at the moment.