红薯4-23 笔试第三题

一、题意，找出长度为n的所有只包含r,g,b三个字符的所有字符串的任意长度子串包含的rgb子序列的个数。
题解：枚举子串左右边界，别的地方随便填，找出本子串里随便填的时候，rgb子序列的个数。

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

const int N = 1005;

int f[N][N][3];

typedef long long LL;

LL qpow(LL x, LL y){
    LL res=1;
    while(y){
        if(y&1)res*=x;
        res%=mod;
        x=x*x%mod;
        y>>=1;
    }

    return res;
}

int main(){
  int n; cin >> n;
  
  if(n<=2){
    cout<<0<<endl;
  }else if(n==3){
    cout<<1<<endl;
  }else{

    for(int i=1;i<=n;++i){
      for(int j=i;j<=n;++j){
       
        f[i][j][0]=(3ll*f[i][j-1][0]+qpow(3,j-i))%mod;
        f[i][j][1]=(3ll*f[i][j-1][1]+f[i][j-1][0])%mod;
        f[i][j][2]=(3ll*f[i][j-1][2]+f[i][j-1][1])%mod;
      }
    }
    
    LL ans=0;
    for(int i=1;i<=n;++i){
      for(int j=i;j<=n;++j){
        ans+=f[i][j][2]*qpow(3,n-(j-i+1));
        ans%=mod;
      }
    }
    
    cout<<ans<<endl;
  }
  
  return 0;
}