結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
👑 ![]() |
提出日時 | 2022-03-01 00:48:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 3,000 ms |
コード長 | 2,332 bytes |
コンパイル時間 | 2,977 ms |
コンパイル使用メモリ | 220,284 KB |
最終ジャッジ日時 | 2025-01-28 03:57:42 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#pragma GCC optimize("Ofast")#define _GLIBCXX_DEBUGusing namespace std;using std::cout;using std::cin;using std::endl;using ll=long long;using ld=long double;ll ILL=1167167167167167167;const int INF=2100000000;const ll mod=1e9+7;#define rep(i,a) for (ll i=0;i<a;i++)template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}else return 0;}template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}void yneos(bool a){if(a) cout<<"Yes\n"; else cout<<"No\n";}string tran(ll a){string S;while(a){S+=(char)('0'+a%10);a/=10;}reverse(S.begin(),S.end());return S;}void solve();// oddloopint main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;rep(i,t) solve();}void solve(){ll N,L,R;cin>>N>>L>>R;ll a=1,b=2,c;vector<string> pref={""};vector<string> p;while(a<=R){string S=tran(a);c=a;swap(a,b);b+=a;if(c<L) continue;p.push_back(S);rep(i,(int)(S.size())){pref.push_back(S.substr(0,i+1));}}So(p);So(pref);pref.erase(unique(pref.begin(),pref.end()),pref.end());int len=pref.size();p.push_back(":");pref.push_back(":");vector<int> ng(len);vector<vector<int>> next(len,vector<int>(10));rep(i,len){int x=pref[i].size();rep(j,x){if(p[LB(p,pref[i].substr(j,x-j))]==pref[i].substr(j,x-j)){ng[i]=1;break;}}rep(k,10){string S=pref[i];S+=(char)('0'+k);next[i][k]=0;rep(j,x+1){int b=LB(pref,S.substr(j,x+1-j));if(pref[b]==S.substr(j,x+1-j)){next[i][k]=b;break;}}}}vector<ll> dp(len);dp[0]=1;rep(i,N){vector<ll> n_dp(len);rep(j,len){dp[j]%=mod;if(dp[j]==0) continue;rep(k,10){if(ng[next[j][k]]) continue;n_dp[next[j][k]]+=dp[j];}}swap(n_dp,dp);}ll ans=mod-1;rep(i,len) ans=(ans+dp[i])%mod;cout<<ans<<"\n";}