Official
E - Chain Contestant Editorial by en_translator
To come to the point, the following bitDP is possible.
dp[for the first \(i\) contests][set of contests participated so far][the kind of last participated contest]={the number of possible combinations}
The transition of DP is as follows.
Let \(x\) be the kind of \(i\)-th contest.
- For every set \(U\) and every kind of contest \(j\), add \(dp[i-1][U][j]\) to \(dp[i][U][j]\) (corresponding to when he does not participate in the \(i\)-th contest)
- If \(j=x\), add \(dp[i-1][U][j]\) to it too (corresponding to when he participate in the \(i\)-th contest, which is the same kind of contest to that he participated last time)
- For every set \(V\) that does not include \(x\) and every kind of contest \(j\), add \(dp[i-1][V][j]\) to \(dp[i][V'][x]\), where \(V'\) is \(V\) with \(x\) added (corresponding to when he participate in the \(i\)-th contest, which is the different kind of contest to that he participated last time)
- Add \(1\) to \(dp[i][W][x]\), where \(W\) is a set only containing \(x\) (corresponding to the case where the first contest he participate in is the \(i\)-th one)
For the bitDP with the transitions above, the final solution is the sum of \(dp[N][U][j]\) over every set \(U\) and every kind of contest \(j\).
The total computational complexity is \(O(2^KNK)\)(\(K=10\), the number of contest types), which fits in the time limit.
Sample code (C++)
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int main(){
int n;
string s;
cin >> n >> s;
long long dp[1024][1024][10]={0};
for(int i=1;i<=n;i++){
int x=s[i-1]-'A';
for(int u=0;u<1024;u++){
for(int j=0;j<10;j++){
dp[i][u][j]=dp[i-1][u][j];
if(j==x){
dp[i][u][j]+=dp[i-1][u][j];
dp[i][u][j]%=mod;
}
}
}
for(int v=0;v<1024;v++){
if(v&(1<<x)){continue;}
for(int j=0;j<10;j++){
dp[i][v|(1<<x)][x]+=dp[i-1][v][j];
dp[i][v|(1<<x)][x]%=mod;
}
}
dp[i][(1<<x)][x]++;
dp[i][(1<<x)][x]%=mod;
}
long long res=0;
for(int u=0;u<1024;u++){
for(int j=0;j<10;j++){res+=dp[n][u][j];res%=mod;}
}
cout << res << '\n';
return 0;
}
posted:
last update: