Medium Counting

　

counting

#include<bits/stdc++.h>
using namespace std;
const int N=55,L=22,C=33,mod=990804011;
char s[N][L];
int n,m,dp[N][N][L][C],a[N][L];
inline int dfs(int l,int r,int p,int c)
{
 int &f=dp[l][r][p][c];
 if(~f)
  return f;
 if(l>r)
  return f=1;
 if(p>m)
  return f=(l==r);
 if(c>26)
  return f=0;
 f=dfs(l,r,p,c+1); 
 for(int i=l;i<=r;i++)
 {
  if(!(a[i][p]==c||(a[i][p]==27&&c)))
   break;
  f=(f+1ll*dfs(l,i,p+1,0)*dfs(i+1,r,p,c+1))%mod;
 }
 return f;
}
int main()
{
 scanf("%d",&n);
 memset(dp,-1,sizeof(dp));
 for(int i=1,l;i<=n;i++)
 {
  scanf("%s",s[i]+1);
  m=max(m,l=strlen(s[i]+1));
  for(int j=1;j<=l;j++)
  {
   if(s[i][j]=='?')
    a[i][j]=27;
   else 
    a[i][j]=s[i][j]-'a'+1;
  }
 }
 printf("%d\n",dfs(1,n,1,0));
 return 0;
}

来源：zr

相关阅读

Linear Counting算法

在上文中，我们知道传统的精确基数计数算法在数据量大时会存在一定瓶颈，瓶颈主要来自于数据结构合并和内存使用两个方面。因此出现了

Counting regions —— 多边形对角线分割区域个数

题目描述 Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to draw a regular polygon with