結果
問題 | No.493 とても長い数列と文字列(Long Long Sequence and a String) |
ユーザー |
![]() |
提出日時 | 2017-03-10 23:33:58 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,144 bytes |
コンパイル時間 | 1,424 ms |
コンパイル使用メモリ | 162,492 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 08:54:50 |
合計ジャッジ時間 | 4,047 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 WA * 69 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef int _loop_int; #define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i) #define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i) #define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i) #define DEBUG(x) cout<<#x<<": "<<x<<endl #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl #define ALL(a) (a).begin(),(a).end() #define CHMIN(a,b) a=min((a),(b)) #define CHMAX(a,b) a=max((a),(b)) // mod const ll MOD = 1000000007ll; #define FIX(a) ((a)%MOD+MOD)%MOD ll k,l,r; ll lensum[125]; ll wasum[125]; ll sekisum[125]; string val[125]; string tos(ll v){ string ret = ""; while(v){ ret = (char)(v%10 + '0') + ret; v/=10; } return ret; } inline pll merge(const pll &a, const pll &b){ return pll((a.first+b.first)%MOD,a.second*b.second%MOD); } pll dfs(int level, int lft){ if(l<=lft && lft+lensum[level]<=r){ return pll(wasum[level],sekisum[level]); }else if(r<=lft || lft+lensum[level]<=l){ return pll(0,1); } pll ret(0,1); ret = merge(ret,dfs(level-1,lft)); lft += lensum[level-1]; if(l<=lft && lft+val[level].size()<=r){ REP(i,val[level].size()){ int yo = val[level][i]-'0'; if(yo==0)yo=10; ret = merge(ret,pll(yo,yo)); } } lft += val[level].size(); ret = merge(ret,dfs(level-1,lft)); return ret; } int main(){ cin>>k>>l>>r; lensum[0] = 0; wasum[0] = 0; sekisum[0] = 1; val[0] = ""; FOR(i,1,k+1){ ll v = i*i; val[i] = tos(v); lensum[i] = 2*lensum[i-1] + val[i].size(); wasum[i] = 2*wasum[i-1]%MOD; sekisum[i] = sekisum[i-1]*sekisum[i-1]%MOD; REP(j,val[i].size()){ int yo = val[i][j]-'0'; if(yo==0)yo=10; wasum[i] = (wasum[i]+yo)%MOD; sekisum[i] = sekisum[i]*yo%MOD; } if(lensum[i]>=r){ k = i; break; } } if(lensum[k]<r){ puts("-1"); return 0; } --l; pll ans = dfs(k,0); printf("%lld %lld\n",ans.first,ans.second); return 0; }