公式
E - Chain Contestant 解説 by physics0523
結論から言うと、以下のような bitDP が成立します。
dp[コンテスト \(i\) 回目まで][既に出場したコンテストの種類の集合][最後に出場したコンテストの種類]={場合の数}
この DP の遷移は以下の通りです。
コンテスト \(i\) 回目の種類が \(x\) である時
- 全ての集合 \(U\) と任意のコンテストの種類 \(j\) に対して、 \(dp[i][U][j]\) に \(dp[i-1][U][j]\) を加算 ( \(i\) 回目のコンテストに出場しないパターン)
- もし \(j=x\) ならさらに \(dp[i-1][U][j]\) を加算 (最後に出場したコンテストと同じ種類の、 \(i\) 回目のコンテストに出場するパターン)
- \(x\) を含まない全ての集合 \(V\) と任意のコンテストの種類 \(j\) に対して、 \(V\) に \(x\) を加えたものを \(V'\) として \(dp[i][V'][x]\) に \(dp[i-1][V][j]\) を加算 (最後に出場したコンテストと異なる種類の、 \(i\) 回目のコンテストに出場するパターン)
- \(x\) のみを含む集合を \(W\) として \(dp[i][W][x]\) に \(1\) を加算 (初めて出場するコンテストが \(i\) 回目であるパターン)
以上の遷移を行う bitDP について、最終的な解は全ての集合 \(U\) と任意のコンテストの種類 \(j\) についての \(dp[N][U][j]\) の総和となります。
計算量は \(O(2^KNK)\) (但し \(K=10\) 、コンテストの種類数)となり、実行時間制限に間に合います。
実装例(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;
}
投稿日時:
最終更新: