結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
![]() |
提出日時 | 2020-10-24 00:13:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 3,000 ms |
コード長 | 2,756 bytes |
コンパイル時間 | 1,457 ms |
コンパイル使用メモリ | 119,508 KB |
実行使用メモリ | 31,360 KB |
最終ジャッジ日時 | 2024-07-21 14:08:21 |
合計ジャッジ時間 | 2,845 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}void add(ll &a,ll b){a=(a+b)%MOD;}void mul(ll &a,ll b){a%=MOD;b%=MOD;a=a*b%MOD;}const int LIM=90;int main(){cin.tie(0);ios::sync_with_stdio(false);vector<ll> F(LIM+1,0);F[0]=1;F[1]=1;for(int i=2;i<LIM;i++) F[i]=F[i-1]+F[i-2];/*rep(i,L){ll val=F[i];bool ok=true;while(val>0){int t=val%10;val/=10;if(t==1||t==2||t==3||t==5||t==8) ok=false;}cout<<F[i]<<endl;if(ok) cout<<i<<endl;}*/int N;ll L,R;cin>>N>>L>>R;vector<ll> A;for(auto p:F){if(L<=p&&p<=R) A.push_back(p);}auto getv=[](ll x){vector<ll> res;while(x>0){res.push_back(x%10);x/=10;}reverse(all(res));return res;};vector<ll> v={0};for(auto x:A){vector<ll> digit=getv(x);ll val=0;for(int i=0;i<digit.size();i++){val=val*10+digit[i];v.push_back(val);}}sort(all(v));v.erase(unique(all(v)),v.end());int V=v.size();map<ll,int> mp;rep(i,V) mp[v[i]]=i;vector<int> bad(V,0);for(auto x:A) bad[mp[x]]=1;vector<vector<int>> g(V,vector<int> (10,-1));for(int i=0;i<V;i++){ll x=v[i];vector<ll> digit=getv(x);reverse(all(digit));for(int nex=0;nex<=9;nex++){if(mp.count(nex)&&bad[mp[nex]]) continue;g[i][nex]=mp[0];ll val=nex;if(mp.count(nex)) g[i][nex]=mp[nex];ll ten=10;for(int d=0;d<digit.size();d++){val=val+ten*digit[d];if(mp.count(val)){if(bad[mp[val]]){g[i][nex]=-1;break;}g[i][nex]=mp[val];}if(val>R) break;ten=ten*10;if(ten>R) break;}}}vector<vector<ll>> dp(N+1,vector<ll> (V+1,0));dp[0][mp[0]]=1;for(int i=0;i<N;i++) for(int j=0;j<V;j++){if(dp[i][j]==0) continue;for(int k=0;k<=9;k++){if(g[j][k]==-1) continue;int nex=g[j][k];add(dp[i+1][nex],dp[i][j]);}}ll ans=0;rep(i,V) add(ans,dp[N][i]);add(ans,MOD-1);cout<<ans<<endl;return 0;}