結果
問題 | No.493 とても長い数列と文字列(Long Long Sequence and a String) |
ユーザー |
![]() |
提出日時 | 2017-03-11 00:08:04 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 800 ms |
コード長 | 2,963 bytes |
コンパイル時間 | 1,446 ms |
コンパイル使用メモリ | 163,828 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 09:11:02 |
合計ジャッジ時間 | 4,236 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 115 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:82:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 82 | scanf("%lld%lld%lld",&k,&l,&r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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]; // ノードの中央の値の文字列 // 簡易解説 // 文字列を生成する木構造を考える // 長さが倍々以上になるので深さはそんなに無いことは容易にわかる // 各ノードが範囲を持つと考えるとお馴染みのsegment treeを範囲探索するアレになる // 範囲和、範囲積は問題なくマージ可能 // それをやるだけ // 実際にノードを全部作るのはやばいしどうせ形が同じなので深さで統一して左側に値が何個あるかを持ってDFS // segment treeと大体同じ感じの議論で訪れるノードはそんなに多くないはず 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,a.second*b.second%MOD); } pll dfs(int level, ll lft){ if(l<=lft && lft+lensum[level]<=r){ // 範囲内 pll ret = pll(wasum[level],sekisum[level]); return ret; }else if(r<=lft || lft+lensum[level]<=l){ // 範囲外 pll ret = pll(0,1); return ret; } // 再帰 pll ret(0,1); ret = merge(ret,dfs(level-1,lft)); lft += lensum[level-1]; REP(i,val[level].size()){ if(l<=lft+i && lft+i<r){ 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(){ scanf("%lld%lld%lld",&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]; 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; 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; }