結果

問題 No.563 超高速一人かるた large
ユーザー Pulmn
提出日時 2017-08-18 23:06:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 137 ms / 3,000 ms
コード長 1,869 bytes
コンパイル時間 875 ms
コンパイル使用メモリ 68,208 KB
実行使用メモリ 163,524 KB
最終ジャッジ日時 2024-10-14 15:01:34
合計ジャッジ時間 3,920 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void Trie::dfs(int, vl&, ll&)’:
main.cpp:46:21: warning: ‘S’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |                 int S;
      |                     ^

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cassert>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const ll mod=1e9+7;
const ll M=2005;
ll C[M][M],P[M][M];
void Init(){
    C[0][0]=P[0][0]=1;
    for(int i=0;i<M;i++) for(int j=0;j<=i;j++) if(i||j){
        if(i>j) C[i][j]=C[i-1][j];
        if(i&&j) (C[i][j]+=C[i-1][j-1])%=mod;
        if(j) P[i][j]=P[i-1][j-1]*i%mod;
        else P[i][j]=1;
    }
}
int n;
class Trie{
    private:
    const int MAX=210000;
    int ID=1;
    vvl date;
    vl a,u,dp;
    void Fix(vl& dp,ll h,int v){
        if(u[v]==1){
            dp[1]=1;
            return;
        }
        for(int i=1;i<dp.size();i++) (dp[i]+=P[u[v]][i]*h%mod*(i-(i==dp.size()-1?1:0)))%=mod;
    }
    void dfs(int v,vl& dp,ll& h){
        if(a[v]==1){
            for(int i=0;i<27;i++) if(date[v][i]!=-1) dfs(date[v][i],dp,h);
            h++;
            return;
        }
        int S;
        bool b=1;
        for(int i=0;i<27;i++){
            int v_=date[v][i];
            if(v_!=-1){
                vl DP(u[v_]+1);
                ll H=0;
                dfs(v_,DP,H);
                Fix(DP,H,v_);
                if(b){
                    dp=DP;
                    b=0;
                    S=u[v_];
                }
                else{
                    vl dp_(S+u[v_]+1);
                    for(int j=0;j<=S;j++) for(int k=0;k<=u[v_];k++) (dp_[j+k]+=(P[u[v_]][k]*dp[j]%mod+P[S][j]*DP[k]%mod)*C[j+k][j])%=mod;
                    S+=u[v_];
                    dp=dp_;
                }
            }
        }
        if(!a[v]) dp=vl(2);
        for(int i=1;i<=u[v];i++) (dp[i]+=(i-(i==u[v]?1:0))*P[u[v]][i])%=mod;
    }
    public:
    Trie(){
        date=vvl(MAX,vl(27,-1));
        a=u=vl(MAX);
    }
    void Update(string s){
        int S=s.size(),I=0;
        u[0]++;
        for(int i=0;i<S;i++){
            int c=s[i]-'a';
            if(date[I][c]==-1){
                date[I][c]=ID++;
                a[I]++;
            }
            I=date[I][c];
            u[I]++;
        }
    }
    void Solve(){
        Init();
        vl dp;
        ll h=0;
        dfs(0,dp,h);
        Fix(dp,h,0);
        for(int i=1;i<=n;i++) cout<<(dp[i]-(i-(i==n?1:0))*P[n][i]%mod+mod)%mod<<endl;
    }
};
int main(){
    cin>>n;
    Trie trie;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        s+="{";
        trie.Update(s);
    }
    trie.Solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0