Description

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表$A$由 $26$个小写英文字母组成$A={a,b,…,z}$。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现$1$次。例如，$a,b,ab,bc,xyz$等字符串都是升序字符串。现在对字母表$A$ 产生的所有长度不超过$6$ 的升序字符串按照字典序排列并编码如下。

对于任意长度不超过 $6$ 的升序字符串，迅速计算出它在上述字典中的编码。对于给定的长度不超过$6$ 的升序字符串，计算出它在上述字典中的编码。

Input

输入数据的第一行是一个正整数$k$，表示接下来共有$k$行。接下来的$k$行中，每行给出一个字符串。

Output

将计算结果输出，共有$k$行，每行对应于一个字符串的编码，对于非法字符串序列输出$0$。

Sample Input

2
a
b

Sample Output

1
2

问题分析

设$f(i,k)$表示以第$i$个字符开头且长度不超过$k$的升序字符串个数,长度不超过$k$的升序字符串的总个数为$sum(k)$,则$sum(k)=\sum_{i=1}^{26}f(i,k)$。

由已知得:

$f(i,1)=1,sum(1)=\sum_{i=1}^{26}f(i,1)=26$
$f(i,2)=\sum_{j=i+1}^{26}f(j,1)=26-i$
$sum(2)=\sum_{i=1}^{26}f(i,2)=\sum_{i=1}^{26}(26-i)=325$
$f(i,3)=\sum_{j=i+1}^{26}f(j,2)$
$sum(3)=\sum_{i=1}^{26}f(i,3)=\sum_{i=1}^{26}\sum_{j=i+1}^{26}f(j,2)$
$......$
$f(i,k)=\sum_{j=i+1}^{26}f(j,k-1)$
$sum(k)=\sum_{i=1}^{26}f(i,k)=\sum_{i=1}^{26}\sum_{j=i+1}^{26}f(j,k-1)$

故可通过递归实现$f(i,k)$和$sum(k)$的计算,因此每一个字符可求出对应的编码,注意初始化结果为$1$且需判断非法字符串

• 第一步: 计算长度小于$k$的升序字符串的总个数

即计算$\sum_{i=1}^{k-1}sum(i)$

• 第二歩: 计算长度等于$k$的字典序小于（即编号在其前面）给定串的总个数

以字符串$bgk$(肯定是合法字符串)为例:
首先是处理首位是$a$,其长度是$3$的情况,即$f(1,3)$;
其次是处理首位是$b$,其剩余长度是$2$的情况分别求出第二位是$c-f$的字符串(注意是升序),即$\sum_{i=3}^{6}f(i,2)$
* 最后是处理首位是$b$,第二位是$g$的,其剩余长度为$1$,分别求出最后一位是$h-j$的字符串(注意是升序),即$\sum_{i=8}^{10}f(i,1)$

官方题解

代码实现

递归实现

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

int t;
ll f[30][10];
ll sum[10];

int check(string str)
{
    for(int i=0;i+1<str.size();i++)
    {
        if(str[i]>=str[i+1])
            return 0;
    }
    return 1;
}

ll dfs(int i,int k)//以i开头,长度不超过k的字符串个数
{
    if(f[i][k]!=0)
        return f[i][k];
    else if(k==1)
        return f[i][k]=1;
    else
    {
        ll temp=0;
        for(int j=i+1;j<=26;j++)
            temp+=dfs(j,k-1);
        return f[i][k]=temp;
    }
}

ll cal(int k)
{
    if(sum[k]!=0)
        return sum[k];
    ll temp=0;
    for(int i=1;i<=26;i++)
        temp+=dfs(i,k);
    return sum[k]=temp;
}



int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        if(check(s)==0)
            cout << 0 << endl;
        else
        {
            int len=s.size();
            ll res=1;
            for(int i=1;i<len;i++)
                res+=cal(i);
            int temp=0;
            for(int i=0;i<len;i++)
            {
                int num=s[i]-'a'+1;
                int len2=len-i;
                for(int j=temp+1;j<num;j++)
                    res+=dfs(j,len2);
                temp=num;
            }
            cout << res << endl;
        }
    }
    return 0;
}

非递归写法

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

int t;
ll f[30][10];
ll sum[10];

int check(string str)
{
    for(int i=0;i+1<str.size();i++)
    {
        if(str[i]>=str[i+1])
            return 0;
    }
    return 1;
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    for(int i=1;i<=26;i++)
        f[i][1]=1;
    sum[1]=26;
    for(int k=2;k<=6;k++)
    {
        for(int i=1;i<=26;i++)
        {
            for(int j=i+1;j<=26;j++)
                f[i][k]+=f[j][k-1];
            sum[k]+=f[i][k];
        }
    }   
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        if(check(s)==0)
            cout << 0 << endl;
        else
        {
            int len=s.size();
            ll res=1;
            for(int i=1;i<len;i++)
                res+=sum[i];
            int temp=0;
            for(int i=0;i<len;i++)
            {
                int num=s[i]-'a'+1;
                int len2=len-i;
                for(int j=temp+1;j<num;j++)
                    res+=f[j][len2];
                temp=num;
            }
            cout << res << endl;
        }
    }
    return 0;
}