結果

問題 No.563 超高速一人かるた large
ユーザー koba-e964koba-e964
提出日時 2017-08-26 00:16:29
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 3,289 bytes
コンパイル時間 1,384 ms
コンパイル使用メモリ 117,740 KB
実行使用メモリ 49,280 KB
最終ジャッジ日時 2024-10-15 16:20:27
合計ジャッジ時間 14,240 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 431 ms
40,704 KB
testcase_01 AC 429 ms
35,328 KB
testcase_02 AC 431 ms
35,328 KB
testcase_03 AC 433 ms
35,456 KB
testcase_04 AC 452 ms
35,584 KB
testcase_05 AC 474 ms
35,712 KB
testcase_06 AC 1,926 ms
38,272 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

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];
ll comb_tbl[N][N];
void init(void) {
  fact[0] = 1;
  REP(i, 1, N) {
    fact[i] = fact[i - 1] * i % mod;
  }
  REP(i, 0, N) {
    REP(j, 0, i + 1) {
      comb_tbl[i][j] = fact[i] * powmod(fact[i - j] * fact[j] % mod, mod - 2)
	% 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 = comb_tbl[j - 1][n - m - 1];;
	  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