結果
問題 | No.2989 Fibonacci Prize |
ユーザー |
|
提出日時 | 2024-12-25 09:36:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 804 ms |
コンパイル使用メモリ | 64,640 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-12-25 09:36:07 |
合計ジャッジ時間 | 3,964 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include<iostream> #include<cassert> using namespace std; int N,M,R; int F[1<<20],S[1<<20]; int cnt[2<<17]; long sum[2<<17]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>M; if(M==1) { cout<<(N==1?2:0)<<endl; return 0; } F[0]=0; F[1]=1%N; for(int i=2;;i++) { F[i]=F[i-1]+F[i-2]; if(F[i]>=N)F[i]-=N; if(F[i-1]==F[0]&&F[i]==F[1]) { R=i-1; break; } } for(int i=1;i<=R;i++) { S[i]=S[i-1]+F[i]; if(S[i]>=N)S[i]-=N; } long ans=0; {//[M,M], [M-2,M-1] if(F[M%R]==0) { ans++; if(M>=3)ans++; } } {//[M-1,M-1] if(F[(M-1)%R]==0)ans++; } //0<=l<r<=M-2, S[l%R]==S[r%R] for(int i=0;i<R;i++)if(i<=M-2) {//i->i long c=(M-2-i)/R+1; ans+=c*(c-1)/2; ans+=sum[S[i]]; ans+=c*(c+1)/2*cnt[S[i]]; sum[S[i]]+=c*(c-1)/2; cnt[S[i]]++; /* for(int j=0;j<i;j++)if(S[i]==S[j]) { long nc=(M-2-j)/R+1; ans+=nc*(nc-1)/2; ans+=c*(c+1)/2; } */ } cout<<ans<<endl; }