题意：
给定一个长度为n ( n < = 1000 )的仅有10种字符的字符串。求子序列的个数，子序列满足相同字母的位置必须相邻。
思路：
下面是样例1 11的13种答案：
B
G
BG
B
BB
GB
H
BH
GH
BGH
BH
BBH
GBH
13
由于字符的种类很少，考虑用状压解决每个字符选o r不选。
假设d p [ i ] [ j ] [ k ]表示从前i ii个位置中选，并且结尾的字母为j ，字母种类的选择情况为k的符合题意的子序列个数。
其中k 是二进制数，该位为1说明该字母已经选择了，为0说明没有选该字母。
对于转移，有三种选择：
当前字母不选，d p [ i ] [ j ] [ k ] = d p [ i − 1 ] [ j ] [ k ]
只选当前字母，d p [ i ] [ n o w ] [ 1 < < n o w ] = d p [ i − 1 ] [ n o w ] [ 1 < < n o w ] + 1
选择当前字母并且从前面的状态转移过来：
当前字母在之前出现过：d p [ i ] [ n o w ] [ j ] = ( d p [ i ] [ n o w ] [ j ] + d p [ i − 1 ] [ n o w ] [ j ] )
没有出现过：d p [ i ] [ n o w ] [ j ∣ 1 < < n o w ] = ( d p [ i ] [ n o w ] [ j ∣ 1 < < n o w ] + d p [ i − 1 ] [ k ] [ j ] )
空间上可以用滚动数组优化掉一维。
代码：
// Problem: E - Chain Contestant // Contest: AtCoder - AtCoder Beginner Contest 215 // URL: https://atcoder.jp/contests/abc215/tasks/abc215_e // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=1e6+7,mod=998244353; char s[1100]; int n,dp[1100][11][1<<11]; int main(){ #ifdef LOCAL freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif cin>>n>>s+1; rep(i,1,n){ int now=s[i]-'A'; rep(j,0,9) repp(k,0,1<<10){ dp[i][j][k]=dp[i-1][j][k];//不选当前字母 } dp[i][now][1<<now]=(dp[i][now][1<<now]+1)%mod;//只选当前字母 repp(j,0,1<<10){ if(j>>now&1){ dp[i][now][j]=(dp[i][now][j]+dp[i-1][now][j])%mod;//当前字母出现过 } else{ rep(k,0,9) if(k!=now) dp[i][now][j|1<<now]=(dp[i][now][j|1<<now]+dp[i-1][k][j])%mod; } } } int ans=0; rep(i,0,9) repp(j,0,1<<10) ans=(ans+dp[n][i][j])%mod; write(ans); return 0; } /* B G BG B BB GB H BH GH BGH BH BBH GBH 13 */
