题解 AT5142 【[AGC035E] Develop】

关怀他人 · 2020-12-22 20:13:39 · 题解

Solution

考虑假如x与x-2最后都要被删除，肯定应该先删x再删x-2，因为如果先删x-2的话，再删x就会又多出来一个x-2）。

考虑建图，连边x \to x-2,x\to x+K，分别表示x要比 x-2,x+K先删。最后如果要求删除的点形成一个环，肯定无解。否则我们按照拓扑序来删必然是一个合法方案。那么原问题相当于对于这样一个图，求有多少点集满足点集内的点不形成环。

考虑与K无关的那些边，会连成1 \gets 3 \gets \cdots与2 \gets 4 \gets \cdots 两条链，一条链上全是奇数，一条链上全是偶数。下面按K的奇偶性讨论，因为K是偶数时x \to x+K这样的边必然是在每条链内部连边，而K为奇数时则是两条链之间的边。

2. 

即对于每个奇数x，将x与x+K放在同一层，注意到环的形式一定为a \to a-2 \to \cdots \to b-K \to b \to b-2 \to \cdots \to a-K \to a（假设a为奇数），对应到图上即从a开始往上走到某一点b-K，再往右走到 b，再往上走到a-K，最后回到a。这相当于一条往上、往右、往上的路径包含大于K + 1个点，就会形成环。 注意到这样一条路径没有往下的选择，所以我们就可以从上到下 dp。设f[i][j][k]表示前i层，往上、往右、往上的路径包含j个点，右边偶数的链对应往上的点连续选中了k个的方案数。设置k这一维是为了方便我们得到新的j（可能在i这个点直接往右走），只有j\leq K+1的状态合法，转移即可。

时间复杂度\mathcal O(n^2K)

Code

int n,K,MOD;
int f[MAXN][MAXN],g[MAXN << 1][MAXN][MAXN];

void Solve1(){
    K /= 2; f[0][0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= K;j++)
            addmod(f[i][0],f[i - 1][j]);
        for(int j = 0;j < K;j++)
            addmod(f[i][j + 1],f[i - 1][j]);
    }
    int sum1 = 0,sum2 = 0;
    for(int i = 0;i <= K;i++)
        addmod(sum1,f[n / 2][i]);
    for(int i = 0;i <= K;i++)
        addmod(sum2,f[(n + 1) / 2][i]);
    printf("%lld\n",1ll * sum1 * sum2 % MOD);
}

void Solve2(){
    g[0][0][0] = 1;
    int cur = 0;
    for(int i = 0;i <= n + K - 2;i += 2){
        cur = i + 2;
        for(int j = 0;j <= n;j++){
            for(int k = 0;k <= K + 1;k++)
                addmod(g[i + 2][0][0],g[i][j][k]);
        }
        if(i + 2 <= n){
            for(int j = 0;j <= n;j++){
                for(int k = 0;k <= K + 1;k++)
                    addmod(g[i + 2][j + 1][0],g[i][j][k]);
            }
        }
        if(i + 2 >= K + 1){
            for(int j = 0;j <= n;j++){
                for(int k = 1;k <= K;k++)
                    addmod(g[i + 2][0][k + 1],g[i][j][k]);
                addmod(g[i + 2][0][0],g[i][j][0]);
            }
        }
        if(i + 2 >= K + 1 && i + 2 <= n){
            for(int j = 0;j <= n;j++){
                for(int k = 0;max(k,j + 1) <= K;k++)
                    addmod(g[i + 2][j + 1][max(k + 1,j + 2)],g[i][j][k]);
            }
        }
    }
    int sum = 0;
    for(int j = 0;j <= n;j++){
        for(int k = 0;k <= K + 1;k++)
            addmod(sum,g[cur][j][k]);
    }
    printf("%d\n",sum);
}

int main(){
    scanf("%d%d%d",&n,&K,&MOD);
    if(K & 1) Solve2();
    else Solve1();
    return 0;
}