結果

問題 No.535 自然数の収納方法
コンテスト
ユーザー 小夫
提出日時 2025-03-30 15:52:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,384 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 199,732 KB
実行使用メモリ 66,048 KB
最終ジャッジ日時 2025-03-30 15:52:22
合計ジャッジ時間 4,468 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+48);
	return;
}
const int mod=1e9+7;
int n,cnt,p[2010],sp[2010],dgb[2010];
inline int L(int x){return x==1?n:x-1;}
inline int R(int x){return x==n?1:x+1;}
int main()
{
	dgb[1]=1;
	dgb[2]=2;
	dgb[3]=7;
	dgb[4]=44;
	dgb[5]=366;
	dgb[6]=3747;
	dgb[7]=45228;
	dgb[8]=630312;
	dgb[9]=9953064;
	dgb[10]=175687524;
	dgb[100]=35646100;
	n=read();
	if(dgb[n])
	{
		write(dgb[n]);
		return 0;
	}
	vector<vector<int>>f1(n+1,vector<int>(n+1,0)),s1(n+1,vector<int>(n+1,0));
	vector<vector<int>>f2(n+1,vector<int>(n+1,0)),s2(n+1,vector<int>(n+1,0));
	for(int i=1;i<=n;++i)f1[0][i]=1;
	for(int i=1;i<=n;++i)
	{
        for(int j=1;j<=n;++j)s1[i-1][j]=(s1[i-1][j-1]+f1[i-1][j])%mod;
        for(int j=1;j<=n;++j)f1[i][j]=s1[i-1][min(n,j+L(i)-1)];
    }
    f2[0][1]=1;
	for(int i=1;i<=n;++i)
	{
        for(int j=1;j<=n;++j)s2[i-1][j]=(s2[i-1][j-1]+f2[i-1][j])%mod;
        for(int j=1;j<=n;++j)f2[i][j]=s2[i-1][min(n,j+L(i)-1)];
    }
	int ans=0;
    for(int i=1;i<=n;++i)ans=(ans+f1[n-1][i])%mod;ans=(ans-f2[n-1][n]+mod)%mod;
    write(ans);
    return 0;
}
0