E. Phoenix and Computers

题目描述

给定 N 台电脑,起初每台电脑都是关闭的

现在你可以随意打开电脑,但如果第 i-1、第 i+1 台电脑一旦开启,则第 i 台电脑也会自动开启,而你无法手动开启它

问你有多少种打开电脑的方法(手动),使得最后所有电脑都是开着的。

Solution

先考虑如果 N 台电脑都要手动开启,有多少种方法?

解法 1:

枚举从哪一台电脑开始打开

如果从 1 开始,那么剩下的必须按照 2,3,…,n 的顺序打开。(如果不按照这个顺序,就会有电脑自动开启)

如果从 2 开始,那么 2 的右边必须按从左往右的顺序开启,即 3,4,…,n ,而 1 可以在这其中任意时刻开启。

一共有C_{n-1}^1 种开启方案

如果从 k 开始,那么 k 的右边必须按照 k+1,k+2,…,n 的顺序开启,k 的左边必须按照 k-1,k-2,…,1 的顺序开启。但是两边的相对的顺序可以改变。

一共有 C_{n-1}^{k-1} 种方案

(一共有 n-1 个电脑需要开启,你先开第 k 个,要为前 k-1 台电脑在剩下 n-1 个顺序(第 2 个开启,第 3 个开启 …)中选出 k-1 个。所以一共有 C_{n-1}^{k-1} 种方案)

所以加起来就是

C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+ … + C_{n-1}^{n-1}=2^{n-1}

解法 2:

归纳法:

考虑 n=1 时,有方案数 k=1

考虑 n=p 时,有方案数 k=x

n=p+1 时,有方案数 k=2*x

如果先关闭了前 p 台电脑,最后关闭了第 p+1 台电脑,这是 x 种方法

如果先关闭了后 p 台电脑,最后关闭了第 1 台电脑,这是 x 种方法

加起来就是 2*x 种方法

所以 n 台电脑就有 2^{n-1} 种方法

如果从左到右看,任何电脑打开的顺序都是这样的。打开几台电脑,自动开启一台,再打开几台电脑,再自动开启一台….也就是手动打开 1\dots i_1 ,自动打开 i_1+1 ,手动打开 i_1+2 \dots i_2,自动打开 i_2+1,….

我们可以通过二项式系数合并手动打开的序列,求出方案数

我们令 dp[len][cnt] 表示打开了前 len 台电脑,其中前 len-1 台电脑中有 cnt 台是手动打开的,第 len 台是自动打开的方案数 ( len

于是有转移 :(在当前状态 ,再手动打开 k 个)

dp[len+k+1][cnt+k]+=dp[len][cnt]*C_{cnt+k}^k*2^{k-1}

根据定义再手动打开 k 个,这 k 个后的 k+1 个就会自动打开,而这 k 个电脑的内部打开顺序的方案数为 2^{k-1} ,而这 k 和前 cnt 个打开的顺序方案是 C_{cnt+k}^k (可以借鉴解法1中的推导)

答案就是

\sum_{i=1}^ndp[n+1][i]

#include<bits/stdc++.h>
#define ll long long
const int N = 410;
ll n,m;
ll C[N][N],bit[N];
ll dp[N][N];
void init(){
    bit[0]=1;
    for(int i=1;i<=n;++i)
        bit[i]=bit[i-1]*2%m;
    C[0][0]=1;
    for(int i=1;i<=n;++i){
        C[i][0]=1;
        for(int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%m;
        }
    }
}
void solve(){
    dp[0][0]=1;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=i;++j){
            for(int k=1;k+i<=n;++k){
                dp[i+k+1][j+k]+=((dp[i][j]*bit[k-1]%m)*C[j+k][k])%m;
                dp[i+k+1][j+k]%=m;
            }
        }
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    init();
    solve();
    ll ans = 0 ;
    for(int i=0;i<=n;++i)
        ans=(ans+dp[n+1][i])%m;
    printf("%lld",ans);
    return 0;
}

题目描述

给定 N 台电脑,起初每台电脑都是关闭的

现在你可以随意打开电脑,但如果第 i-1、第 i+1 台电脑一旦开启,则第 i 台电脑也会自动开启,而你无法手动开启它

问你有多少种打开电脑的方法(手动),使得最后所有电脑都是开着的。

Solution

先考虑如果 N 台电脑都要手动开启,有多少种方法?

解法 1:

枚举从哪一台电脑开始打开

如果从 1 开始,那么剩下的必须按照 2,3,…,n 的顺序打开。(如果不按照这个顺序,就会有电脑自动开启)

如果从 2 开始,那么 2 的右边必须按从左往右的顺序开启,即 3,4,…,n ,而 1 可以在这其中任意时刻开启。

一共有C_{n-1}^1 种开启方案

如果从 k 开始,那么 k 的右边必须按照 k+1,k+2,…,n 的顺序开启,k 的左边必须按照 k-1,k-2,…,1 的顺序开启。但是两边的相对的顺序可以改变。

一共有 C_{n-1}^{k-1} 种方案

(一共有 n-1 个电脑需要开启,你先开第 k 个,要为前 k-1 台电脑在剩下 n-1 个顺序(第 2 个开启,第 3 个开启 …)中选出 k-1 个。所以一共有 C_{n-1}^{k-1} 种方案)

所以加起来就是

C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+ … + C_{n-1}^{n-1}=2^{n-1}
解法 2:

归纳法:

考虑 n=1 时,有方案数 k=1

考虑 n=p 时,有方案数 k=x

n=p+1 时,有方案数 k=2*x

如果先关闭了前 p 台电脑,最后关闭了第 p+1 台电脑,这是 x 种方法

如果先关闭了后 p 台电脑,最后关闭了第 1 台电脑,这是 x 种方法

加起来就是 2*x 种方法

所以 n 台电脑就有 2^{n-1} 种方法

如果从左到右看,任何电脑打开的顺序都是这样的。打开几台电脑,自动开启一台,再打开几台电脑,再自动开启一台….也就是手动打开 1\dots i_1 ,自动打开 i_1+1 ,手动打开 i_1+2 \dots i_2,自动打开 i_2+1,….

我们可以通过二项式系数合并手动打开的序列,求出方案数

我们令 dp[len][cnt] 表示打开了前 len 台电脑,其中前 len-1 台电脑中有 cnt 台是手动打开的,第 len 台是自动打开的方案数 ( len

于是有转移 :(在当前状态 ,再手动打开 k 个)
dp[len+k+1][cnt+k]+=dp[len][cnt]_C_{cnt+k}^k_2^{k-1}
根据定义再手动打开 k 个,这 k 个后的 k+1 个就会自动打开,而这 k 个电脑的内部打开顺序的方案数为 2^{k-1} ,而这 k 和前 cnt 个打开的顺序方案是 C_{cnt+k}^k (可以借鉴解法1中的推导)

答案就是
\sum_{i=1}^ndp[n+1][i]

#include<bits/stdc++.h>
#define ll long long
const int N = 410;
ll n,m;
ll C[N][N],bit[N];
ll dp[N][N];
void init(){
    bit[0]=1;
    for(int i=1;i<=n;++i)
        bit[i]=bit[i-1]*2%m;
    C[0][0]=1;
    for(int i=1;i<=n;++i){
        C[i][0]=1;
        for(int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%m;
        }
    }
}
void solve(){
    dp[0][0]=1;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=i;++j){
            for(int k=1;k+i<=n;++k){
                dp[i+k+1][j+k]+=((dp[i][j]*bit[k-1]%m)*C[j+k][k])%m;
                dp[i+k+1][j+k]%=m;
            }
        }
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    init();
    solve();
    ll ans = 0 ;
    for(int i=0;i<=n;++i)
        ans=(ans+dp[n+1][i])%m;
    printf("%lld",ans);
    return 0;
}
分类: DP计数

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注