結果
問題 |
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 |
ソースコード
#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; }