Submission #73556859

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i=0; i<(int)n; i++)

int main(){
  int n,l;
  cin >> n >> l;
  vector<string> s(n),S;
  rep(i,n) cin >> s[i];
  // ほかの文字列に含まれる文字列は無視
  vector<bool> ic(n);
  rep(i,n)rep(j,n){
    if(s[j].size()>s[i].size())rep(k,s[j].size()-s[i].size()+1){
      bool ok=1;
      rep(m,s[i].size())if(s[i][m]!=s[j][m+k]) ok=0;
      if(ok) ic[i]=1;
    }
  }
  rep(i,n)if(!ic[i]) S.push_back(s[i]);
  n=S.size();
  
  // 何文字重複できるか前計算
  vector<vector<vector<int>>> dup(n,vector<vector<int>>(n));
  rep(i,n)rep(j,n){
    int bd=min(S[i].size(),S[j].size());
    rep(k,bd){
      bool ok=1;
      rep(m,k) if(S[i][S[i].size()-k+m]!=S[j][m]) ok=0;
      if(k>0&&ok) dup[i][j].push_back(k);
    }
  }
  
  // DPの遷移(文字列の添え字は0-indexedとなっていて、j=-1はここではj=nとして扱う)
  vector<vector<vector<mint>>> dp(l+1,vector<vector<mint>>(1<<n,vector<mint>(n+1)));
  dp[0][0][n]=1;
  for(int i=1; i<=l; i++){
    rep(t,1<<n)rep(j,n)if(t&(1<<j)){
      if(i<S[j].size()) continue;
      dp[i][t][j]+=dp[i-S[j].size()][t-(1<<j)][n];
      rep(k,n)if((t-(1<<j))&(1<<k)) dp[i][t][j]+=dp[i-S[j].size()][t-(1<<j)][k];
      rep(k,n){
        for(int m:dup[k][j]){
          if((t-(1<<j))&(1<<k)) dp[i][t][j]+=dp[i-S[j].size()+m][t-(1<<j)][k];
          else dp[i][t][j]-=dp[i-S[j].size()+m][t-(1<<j)+(1<<k)][k];
        }
      }
    }
    rep(t,1<<n){
      dp[i][t][n]+=dp[i-1][t][n]*26;
      rep(k,n){
        if(t&(1<<k)) dp[i][t][n]+=dp[i-1][t][k]*26;
        else dp[i][t][n]-=dp[i][t+(1<<k)][k];
      }
    }
  }
  mint ans=0;
  rep(k,n+1) ans+=dp[l][(1<<n)-1][k];
  cout << ans.val() << endl;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:6:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i,n) for (int i=0; i<(int)n; i++)
      |                                 ^
./Main.cpp:16:32: note: in expansion of macro 'rep'
   16 |     if(s[j].size()>s[i].size())rep(k,s[j].size()-s[i].size()+1){
      |                                ^~~
./Main.cpp:41:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |       if(i<S[j].size()) continue;
      |          ~^~~~~~~~~~~~

Judge Result