結果

問題 No.563 超高速一人かるた large
ユーザー HIR180
提出日時 2017-08-25 23:25:54
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0