結果

問題 No.563 超高速一人かるた large
ユーザー HIR180HIR180
提出日時 2017-08-25 23:25:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 942 ms / 3,000 ms
コード長 3,300 bytes
コンパイル時間 1,704 ms
コンパイル使用メモリ 169,904 KB
実行使用メモリ 66,880 KB
最終ジャッジ日時 2024-10-15 16:12:20
合計ジャッジ時間 8,303 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
15,896 KB
testcase_01 AC 33 ms
13,848 KB
testcase_02 AC 33 ms
15,936 KB
testcase_03 AC 39 ms
18,264 KB
testcase_04 AC 51 ms
20,928 KB
testcase_05 AC 61 ms
21,476 KB
testcase_06 AC 202 ms
31,884 KB
testcase_07 AC 259 ms
36,700 KB
testcase_08 AC 517 ms
51,820 KB
testcase_09 AC 942 ms
66,464 KB
testcase_10 AC 182 ms
63,176 KB
testcase_11 AC 186 ms
65,272 KB
testcase_12 AC 173 ms
65,736 KB
testcase_13 AC 262 ms
66,004 KB
testcase_14 AC 158 ms
66,384 KB
testcase_15 AC 132 ms
66,880 KB
testcase_16 AC 214 ms
66,780 KB
testcase_17 AC 427 ms
28,032 KB
testcase_18 AC 774 ms
66,616 KB
testcase_19 AC 245 ms
12,860 KB
testcase_20 AC 491 ms
52,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
string str[2005];

int NN,k;
int ran[300005];
int tmp[300005];
int sa[300005];

bool compare_sa(int i,int j)
{
	if(ran[i] != ran[j]) return ran[i] < ran[j];
	else
	{
		int ri = i+k<=NN ? ran[i+k]: -1;
		int rj = j+k<=NN ? ran[j+k]: -1;
		
		return ri < rj;
	}
}

void construct_sa(string S)
{
	NN = S.size();
	for(int i=0;i<=NN;i++)
	{
		sa[i] = i;
		ran[i] = i<NN?S[i]:-1;
	}
	
	for(k=1;k<=NN;k*=2)
	{
		sort(sa,sa+NN+1,compare_sa);
		
		tmp[sa[0]] = 0;
		for(int i=1;i<=NN;i++)
		{
			tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
		}
		for(int i=0;i<=NN;i++)
		{
			ran[i] = tmp[i];
		}
	}
}
int lcp[300005];
void construct_lcp(string S)
{
	int n = S.size();
	for(int i=0;i<=n;i++) ran[sa[i]] = i;
	
	int h = 0;
	lcp[0] = 0;
	
	for(int i=0;i<n;i++)
	{
		int j = sa[ran[i]-1];
		
		if(h) h--;
		for(;j+h<n && i+h<n;h++)
		{
			if(S[j+h] != S[i+h]) break;
		}
		lcp[ran[i]-1] = h;
	}
}
#define mod 1000000007
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[200005],R[200005];
void make(){
	F[0] = 1;
	for(int i=1;i<200005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<200005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}
int ML[2005][2005];
int cnt[2005][2005];
ll FF[2005][2005];
ll ans[2005];
string S;
int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> str[i];
		S += str[i];
		S += "*";
	}
	construct_sa(S);
	construct_lcp(S);
	vector<P>RR;int cur = 0;
	for(int i=0;i<n;i++){
		RR.pb(mp(ran[cur],i));
		cur += str[i].size()+1;
	}
	sort(RR.begin(),RR.end());
	for(int i=0;i<RR.size();i++){
		int val = INF,nxt = RR[i].fi;
		for(int j=i+1;j<RR.size();j++){
			while(nxt < RR[j].fi){
				val = min(val,lcp[nxt++]);
			}
			ML[RR[i].sc][RR[j].sc] = ML[RR[j].sc][RR[i].sc] = val;
		}
	}
	make();
	for(int k=1;k<=n;k++){
		for(int l=0;l<k;l++){
			FF[k][l] = C(k,l+1)*F[l]%mod*F[n-l-1]%mod*R[n-k]%mod;
		}
		for(int l=k;l<=n;l++){
			FF[k][l] = 0;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j) continue;
			cnt[i][ML[i][j]+1]++;
		}
	}
	for(int i=0;i<n;i++){
		for(int k=1;k<=n;k++){
			ans[k] += (ll)(str[i].size()+1) * FF[k][0] % mod;
			ans[k] %= mod;//if(k==3) cout << ans[k] << endl;
			int L = 0;
			for(int x=str[i].size()+1;x>=2;x--){
				L += cnt[i][x];
				ans[k] -= FF[k][L]; //if(k==3) cout << ans[k] << endl;
			}
			
		}
	}
	for(int k=1;k<=n;k++){
		cout << (ans[k]%mod+mod)%mod << endl;
	}
}
0