結果

問題 No.563 超高速一人かるた large
ユーザー kotatsugamekotatsugame
提出日時 2020-04-22 17:48:44
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 3 ms
6,816 KB
testcase_05 AC 4 ms
6,820 KB
testcase_06 AC 14 ms
6,820 KB
testcase_07 AC 20 ms
6,820 KB
testcase_08 AC 38 ms
6,816 KB
testcase_09 AC 65 ms
6,820 KB
testcase_10 AC 55 ms
6,820 KB
testcase_11 AC 62 ms
6,820 KB
testcase_12 AC 62 ms
6,820 KB
testcase_13 AC 62 ms
6,820 KB
testcase_14 AC 61 ms
6,820 KB
testcase_15 AC 61 ms
6,820 KB
testcase_16 AC 62 ms
6,820 KB
testcase_17 AC 13 ms
6,820 KB
testcase_18 AC 66 ms
6,816 KB
testcase_19 AC 6 ms
6,816 KB
testcase_20 AC 39 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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