結果

問題 No.563 超高速一人かるた large
コンテスト
ユーザー koba-e964
提出日時 2017-08-26 00:11:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,188 bytes
コンパイル時間 1,350 ms
コンパイル使用メモリ 118,380 KB
実行使用メモリ 13,632 KB
最終ジャッジ日時 2024-10-15 16:19:47
合計ジャッジ時間 7,766 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

ll powmod(ll a, ll e) {
  ll sum = 1;
  ll cur = a;
  while (e > 0) {
    if (e % 2) {
      sum = sum * cur % mod;
    }
    cur = cur * cur % mod;
    e /= 2;
  }
  return sum;
}


const int N = 2437;
ll fact[N];
void init(void) {
  fact[0] = 1;
  REP(i, 1, N) {
    fact[i] = fact[i - 1] * i % mod;
  }
}


const int DEBUG = 0;

vector<VI> get_lcp(const vector<pair<string, int> > &pool) {
  int n = pool.size();
  vector<VI> lcp(n, VI(n));
  VI neighbor(n - 1);
  REP(i, 0, n - 1) {
    const string& u = pool[i].first;
    const string& v = pool[i + 1].first;
    int idx = 0;
    while (true) {
      if ((int) u.length() <= idx || (int) v.length() <= idx) {
	break;
      }
      if (u[idx] == v[idx]) {
	idx += 1;
      } else {
	break;
      }
    }
    neighbor[i] = idx;
  }
  REP(i, 0, n - 1) {
    int cur = 1e8;
    REP(j, i + 1, n) {
      cur = min(cur, neighbor[j - 1]);
      lcp[pool[i].second][pool[j].second] = cur;
      lcp[pool[j].second][pool[i].second] = cur;
    }
  }
  REP(i, 0, n) {
    int idx = pool[i].second;
    lcp[idx][idx] = pool[i].first.size();
  }
  return lcp;
}

int main(void) {
  init();
  int n;
  cin >> n;
  vector<string> s(n);
  vector<pair<string, int> > pool(n);
  REP(i, 0, n) {
    cin >> s[i];
    s[i] += '$';
    pool[i] = make_pair(s[i], i);
  }
  sort(pool.begin(), pool.end());
  vector<VI> lcp = get_lcp(pool);
  if (DEBUG) {
    REP(i, 0, n) {
      cerr << "lcp[" << i << "]:";
      REP(j, 0, n) {
	cerr << " " << lcp[i][j];
      }
      cerr << endl;
    }
  }
  REP(i, 0, n) {
    VI tap = lcp[i];
    sort(tap.begin(), tap.end());
    tap.pop_back(); // drop i itself
    lcp[i] = tap;
  }
  vector<ll> dp(n + 1);
  dp[0] = 0;
  REP(m, 1, n + 1) {
    if (DEBUG) {
      cerr << "** m = " << m << endl;
    }
    ll tot = (n - m + 1) * dp[m - 1] % mod;
    ll fac = fact[m - 1];
    REP(i, 0, n) {
      // exhaustive search of S s.t. i \in S, |S| = m
      VI tap = lcp[i];
      if (DEBUG) {
	cerr << "tap:";
	for(auto v:tap)cerr<<" " <<v;
	cerr<<endl;
      }
      ll loctot = 0;
      if (DEBUG) {
	cerr << "i = " << i << endl;
      }
      if(m < n) {
	REP(j, n - m, n) {
	  // C(j - 1, n - m - 1)
	  ll comb = fact[j - 1] *
	    powmod(fact[n - m - 1] * fact[j - n + m] % mod, mod - 2) % mod;
	  if (DEBUG) {
	    cerr << "j = " << j << endl;
	    cerr << "taploc " << tap[j - 1] << " " << comb << endl;
	  }
	  loctot += (tap[j - 1] + 1) * comb % mod;
	  loctot %= mod;
	}
      } else {
	loctot = 1;
      }
      tot += loctot * fac % mod;
      tot %= mod;
    }
    dp[m] = tot;
  }
  REP(i, 1, n + 1) {
    cout << dp[i] % mod << endl;
  }
}
0