結果

問題 No.535 自然数の収納方法
コンテスト
ユーザー 小夫
提出日時 2025-03-30 16:24:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 1,289 bytes
コンパイル時間 2,232 ms
コンパイル使用メモリ 199,496 KB
実行使用メモリ 65,920 KB
最終ジャッジ日時 2025-03-30 16:24:31
合計ジャッジ時間 4,281 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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];
int main()
{
	//freopen("number.in","r",stdin);
	//freopen("number.out","w",stdout);
	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[1][i]=1;
	f2[1][1]=1;
	for(int i=2;i<=n;++i)
	{
        for(int j=1;j<=n;++j)s1[i-1][j]=(s1[i-1][j-1]+f1[i-1][j])%mod,s2[i-1][j]=(s2[i-1][j-1]+f2[i-1][j])%mod;
        for(int j=1;j<=n;++j)f1[i][j]=s1[i-1][min(n,j+max(i-2,1)-1)],f2[i][j]=s2[i-1][min(n,j+max(i-2,1)-1)];
    }
	int ans=0;
    for(int i=1;i<=n;++i)ans=(ans+f1[n][i])%mod;ans=(ans-f2[n][n]+mod)%mod;
    write(ans);
    return 0;
}
0