結果
問題 |
No.554 recurrence formula
|
ユーザー |
![]() |
提出日時 | 2017-08-12 00:28:33 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 825 bytes |
コンパイル時間 | 958 ms |
コンパイル使用メモリ | 57,036 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 22:33:46 |
合計ジャッジ時間 | 1,191 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream> #include <cstdio> using namespace std; #define M 1e9+7 long long int N; long long int a[100001],b[100001]; long long int ans; long long int mod=M; void add(long long int *bit,int i,long long int x){ while(i<=N){ bit[i]+=x; bit[i]%=mod; i+=i&-i; } } long long int sum(long long int *bit ,int i){ long long int s=0; while(i>0){ s+=bit[i]; s%=mod; i -=i& -i; } return s%mod; } int main(){ for(int i=0;i<100001;i++){a[i]=0;b[i]=0;} cin >> N; add(a,1,1); if(N==1){ cout << "1" << endl; return 0; } for(int i=2;i<=N;i++){ if(i%2==0){ ans=i*sum(a,i/2); ans%=mod; add(b,i/2,ans%mod); } else{ ans=i*sum(b,i/2); ans%=mod; add(a,i/2+1,ans%mod); } if(i==N)cout << ans%mod << endl; } return 0; }