Keep at Most 100 Characters

Given a string which contains only lower case letters, how many different non-empty strings you can get if you can keep AT MOST 100 characters in the original order? (Note: The string obtained is a "sub-sequence" of the original string.)

Input Specification:

Each input file contains one test case, which is only one line containing the string whose length is no larger than 1000.

Output Specification:

Output the number of different non-empty strings if you can only keep at most 100 characters. Since the answer might be super large, you only need to output the answer modulo 1000000007.

Sample Input:

aabac

Sample Output:

19

Hint:

The strings are:

a, b, c, aa, ab, ac, ba, bc, aab, aaa, aac, aba, abc, bac, aaba, aabc, abac, aaac, and aabac.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 1000000007u
 4 int main()
 5 {
 6 //    freopen("data.txt","r",stdin);
 7     char a[1001];
 8     scanf("%s",a);
 9     int asl=strlen(a)+1;
10     long long op=0;
11     int masl=min(asl,101);
12     vector<long long> v(asl*masl,1);
13     for(int i=1;i<masl;i++)
14     {
15         vector<long long> maxre(26,0);
16         maxre[a[i-1]-‘a‘]=1;
17         for(int j=i+1;j<asl;j++)
18         {
19             v[i*asl+j]=(v[i*asl+j-1]+v[(i-1)*asl+j-1]-maxre[a[j-1]-‘a‘]+mod)%mod;
20             maxre[a[j-1]-‘a‘]=v[(i-1)*asl+j-1];
21         }
22     }
23     for(int i=1;i<masl;i++)
24     op=(op+v[(i+1)*asl-1])%mod;    
25     printf("%lld",op);
26     return 0;
27 }
28  

Keep at Most 100 Characters

原文：https://www.cnblogs.com/SkystarX/p/12285761.html