牛客提高D6t2 破碎的序列

分析

我们不难发现对于偶数的情况只要相邻两个数不相等即可

而对于奇数的情况只要中间恰好隔一个数的两个数不相等即可

于是我们又dp[i][0/1]表示考虑到第i位,这一位和它后面离它最近的一个确定的数是否相等

每次从i-1转移即可

注意对于奇数的情况最终答案要n-1和n的dp值相乘以保证合法

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int mod = ;

int dp[][],a[],b[],n,m,k;

int main(){

    int i,j;

    scanf("%d%d%d",&n,&k,&m);

    for(i=;i<=n;i++)scanf("%d",&a[i]);

    if(m==){

      for(i=n-;i>;i--)b[i]=a[i+]?a[i+]:b[i+];

      if(a[]&&a[]==b[]){

        dp[][]=;

        dp[][]=;

      }else if(a[]){

        dp[][]=;

        dp[][]=;

      }else {

        dp[][]=;

        dp[][]=k-;

      }

      for(i=;i<=n;i++)

        if(a[i]&&a[i]==b[i]){

          dp[i][]=;

          dp[i][]=dp[i-][];

        }else if(a[i]){

          dp[i][]=;

          dp[i][]=dp[i-][];

        }else {

          dp[i][]=dp[i-][];

          dp[i][]=((dp[i][]+1ll*dp[i-][]*(k-)%mod)%mod+1ll*dp[i-][]*(k-)%mod)%mod;

        }

      printf("%d\n",(dp[n][]+dp[n][])%mod);

    }else {

      for(i=n-;i>;i--)b[i]=a[i+]?a[i+]:b[i+];

      for(i=;i<=;i++){

        if(a[i]&&a[i]==b[i]){

          dp[i][]=;

          dp[i][]=;

        }else if(a[i]){

          dp[i][]=;

          dp[i][]=;

        }else {

          dp[i][]=;

          dp[i][]=k-;

        }

      }

      for(i=;i<=n;i++)

        if(a[i]&&a[i]==b[i]){

          dp[i][]=;

          dp[i][]=dp[i-][];

        }else if(a[i]){

          dp[i][]=;

          dp[i][]=dp[i-][];

        }else {

          dp[i][]=dp[i-][];

          dp[i][]=((dp[i][]+1ll*dp[i-][]*(k-)%mod)%mod+1ll*dp[i-][]*(k-)%mod)%mod;

        }

      printf("%d\n",1ll*((dp[n][]+dp[n][])%mod)*((dp[n-][]+dp[n-][])%mod)%mod);

    }

    return ;

}

巴特西

牛客提高D6t2 破碎的序列

最新文章

热门文章