Hướng dẫn cho Dãy đèn (OLP MT&TN 2022 CT)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Flower_On_Stone

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];
}

Bình luận

Không có bình luận nào.