結果

問題 No.563 超高速一人かるた large
コンテスト
ユーザー kotatsugame
提出日時 2020-04-22 17:48:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 66 ms / 3,000 ms
コード長 1,234 bytes
コンパイル時間 954 ms
コンパイル使用メモリ 78,576 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-11 21:48:41
合計ジャッジ時間 2,793 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const long mod=1e9+7;
int N;
string s[2000];
int h[2000];
long X[2020];
long ans[2020];
long inv[2020];
main()
{
	cin>>N;
	inv[1]=1;
	for(int i=2;i<=N;i++)inv[i]=mod-mod/i*inv[mod%i]%mod;
	for(int i=0;i<N;i++)cin>>s[i];
	sort(s,s+N);
	for(int i=0;i<N-1;i++)
	{
		int j=0;
		while(j<s[i].size()&&j<s[i+1].size()&&s[i][j]==s[i+1][j])j++;
		h[i]=j;
	}
	for(int i=0;i<N;i++)
	{
		int l=i-1,r=i+1;
		int id=0;
		int lm=s[i].size(),rm=s[i].size();
		while(l>=0||r<N)
		{
			int L=l>=0?h[l]:0;
			int R=r<N?h[r-1]:0;
			lm=min(lm,L);
			rm=min(rm,R);
			if(l<0)
			{
				(X[id]+=rm+1)%=mod;
				r++;
			}
			else if(r>=N)
			{
				(X[id]+=lm+1)%=mod;
				l--;
			}
			else
			{
				if(lm<rm)
				{
					(X[id]+=rm+1)%=mod;
					r++;
				}
				else
				{
					(X[id]+=lm+1)%=mod;
					l--;
				}
			}
			id++;
		}
	}
	for(int i=0;i<N-1;i++)
	{
		long Q=1;
		for(int j=1;j<=i;j++)Q=Q*j%mod;
		for(int j=i;j<=N-2;j++)
		{
			(ans[j]+=X[i]*Q)%=mod;
			Q=Q*(N-2-j)%mod*inv[j-i+1]%mod;
			Q=Q*(j+1)%mod;
		}
	}
	long P=1;
	for(int i=0;i<N-1;i++)
	{
		P=P*(i+1)%mod;
		(ans[i+1]+=ans[i]*(N-1-i))%=mod;
	}
	(ans[N-1]+=N*P)%=mod;
	for(int i=0;i<N;i++)cout<<ans[i]<<endl;
}
0