結果

問題 No.563 超高速一人かるた large
ユーザー koyumeishikoyumeishi
提出日時 2017-06-18 15:09:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 3,000 ms
コード長 3,240 bytes
コンパイル時間 1,339 ms
コンパイル使用メモリ 118,664 KB
実行使用メモリ 34,012 KB
最終ジャッジ日時 2024-10-01 20:00:24
合計ジャッジ時間 3,150 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <random>
#include <algorithm>
#include <set>
#include <map>
#include <chrono>
using namespace std;

void timer(){
  static chrono::steady_clock::time_point start = chrono::steady_clock::now();
  auto now = chrono::steady_clock::now();
  cerr << "elapsed time : " << chrono::duration_cast<chrono::milliseconds>(now-start).count() << "[ms]" << endl;
}

const long long mod = 1000000007;

long long ans[10001];
long long fact[10001];
long long fact_inv[10001];
// long long nCr_[10001][10001];

long long mod_pow(long long x, long long y, long long mod){  //(x^y) % mod
  if(x==0 && y!=0) return 0;
  long long ret=1LL;
  while(y>0LL){
    if(y&1LL) ret = (ret * x) % mod;
    x = (x*x) % mod;
    y >>= 1LL;
  }
  return ret;
}

long long nCr(long long n, long long r){
  // if(nCr_[n][r]) return nCr_[n][r];
  return fact[n] * fact_inv[r] % mod * fact_inv[n-r] % mod;
}

struct trie_node{
  map<char, int> child;
  int count;
};
vector<trie_node> trie;

vector<long long> s[200001];
vector<long long> w[200001];

// dp[i][x] := i 頂点で合計長 x の組み合わせ
void dfs(int pos, long long d){
  if( trie[pos].count == 1 ){
    w[pos].resize(2);
    s[pos].resize(2);
    w[pos][0] = w[pos][1] = 1;
    s[pos][0] = 0; s[pos][1] = 1;
    return;
  }
  if( trie[pos].child.size() == 1 ){
    int nx = trie[pos].child.begin()->second;
    dfs(nx, d+1);
    swap( s[pos], s[nx] );
    swap( w[pos], w[nx] );
    return;
  }

  w[pos].resize(1);
  s[pos].resize(1);
  w[pos][0] = 1;
  s[pos][0] = 0;

  for(auto p : trie[pos].child){
    if( p.first == '}' ) continue;

    vector<long long> w_, s_;

    int nx = p.second;
    dfs(nx, 1);

    for(int i=0; i<w[pos].size(); i++){
      for(int j=0; j<w[nx].size(); j++){
        if(i+j >= w_.size()){
          w_.resize(i+j+1);
          s_.resize(i+j+1);
        }
        (w_[i+j] += w[pos][i] * w[nx][j] % mod * nCr(i+j, i) % mod) %= mod;
        (s_[i+j] += s[pos][i] * w[nx][j] % mod * nCr(i+j, i) % mod) %= mod;
        (s_[i+j] += w[pos][i] * s[nx][j] % mod * nCr(i+j, i) % mod) %= mod;
      }
    }
    swap(w[pos], w_);
    swap(s[pos], s_);
  }

  w[pos].resize( trie[pos].count + 1 );
  s[pos].resize( trie[pos].count + 1 );
  for(long long i=1; i<w[pos].size(); i++){
    (s[pos][i] += d*min<long long>(i, trie[pos].count-1)%mod * w[pos][i]) %= mod;
  }
}

int main(){
  timer();

  fact[0] = fact_inv[0] = 1;
  for(int i=1; i<10001; i++){
    fact[i] = fact[i-1] * i % mod;
    fact_inv[i] = mod_pow(fact[i],mod-2,mod);
  }

  int n;
  cin >> n;
  vector<string> s_(n);
  for(int i=0; i<n; i++){
    cin >> s_[i];
    s_[i] += '{';
  }
  s_.push_back("}");

  trie.push_back( trie_node{{}, 0} );
  for(int i=0; i<s_.size(); i++){
    int pos = 0;
    for(int j=0; j<s_[i].size(); j++){
      trie[pos].count++;
      if( trie[pos].child.count( s_[i][j] ) == 0 ){
        trie.push_back( trie_node{ {}, 0} );
        trie[pos].child[s_[i][j]] = trie.size()-1;
      }
      pos = trie[pos].child[s_[i][j]];
    }
    trie[pos].count++;
  }

  dfs(0, 0);

  for(int i=1; i<=n; i++){
    ans[i-1] = s[0][i];
  }

  for(int i=0; i<n; i++) cout << ans[i]%mod << endl;

  timer();
  return 0;
}
0