結果
| 問題 | No.493 とても長い数列と文字列(Long Long Sequence and a String） |
| ユーザー |
 sntea
|
| 提出日時 | 2019-10-22 00:24:09 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 800 ms |
| コード長 | 6,947 bytes |
| コンパイル時間 | 2,231 ms |
| コンパイル使用メモリ | 190,980 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-02 17:53:24 |
| 合計ジャッジ時間 | 5,357 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 115 |
ソースコード
#ifdef LOCAL111#define _GLIBCXX_DEBUG#else#pragma GCC optimize ("O3")#define NDEBUG#endif// #define _USE_MATH_DEFINES#include <bits/stdc++.h>const int INF = 1e9;using namespace std;template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }#define endl '\n'#define ALL(a) (a).begin(),(a).end()#define SZ(a) int((a).size())#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)#define REP(i,n) FOR(i,0,n)#define RREP(i,n) for (int i=(n)-1;i>=0;i--)#ifdef LOCAL111#define DEBUG(x) cout<<#x<<": "<<(x)<<endltemplate<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}#else#define DEBUG(x) truetemplate<typename T> void dpite(T a, T b){ return; }#endif#define F first#define S second#define SNP string::npos#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}template<typename T,typename U,typename... V>typename enable_if<is_same<T, U>::value!=0>::typefill_v(U &u,const V... v){u=U(v...);}template<typename T,typename U,typename... V>typename enable_if<is_same<T, U>::value==0>::typefill_v(U &u,const V... v){for(auto &e:u) fill_v<T>(e,v...);}const array<int, 4> dx = {0, 1, 0, -1};const array<int, 4> dy = {1, 0, -1, 0};typedef long long int LL;typedef unsigned long long ULL;typedef pair<int,int> P;void ios_init(){//cout.setf(ios::fixed);//cout.precision(12);#ifdef LOCAL111return;#endifios::sync_with_stdio(false); cin.tie(0);}template<long long MOD>class ModInt {public:const static long long mod = MOD;long long x;ModInt() {x = 0;}ModInt(long long x) {x %= mod;this->x = x < 0 ? x+mod : x;}int get() const {return (int)x;}ModInt &operator+=(ModInt that) {if((x += that.get()) >= mod) x -= mod;return *this;}ModInt &operator-=(ModInt that) {if((x += mod-that.get()) >= mod) x -= mod;return *this;}ModInt &operator*=(ModInt that) {x = x*that.get()%mod;return *this;}ModInt &operator/=(ModInt that) {return *this *= that.inverse();}ModInt operator+(ModInt that) const {return ModInt(*this) += that;}ModInt operator-(ModInt that) const {return ModInt(*this) -= that;}ModInt operator*(ModInt that) const {return ModInt(*this) *= that;}ModInt operator/(ModInt that) const {return ModInt(*this) /= that;}ModInt inverse() const {using std::swap;long long a = x, b = mod, u = 1, v = 0;while(b) {long long t = a/b;a -= t*b; swap(a,b);u -= t*v; swap(u,v);}return ModInt(u);}ModInt pow(int n) const{ModInt b = *this;ModInt res = 1;while(n != 0) {if(n&1){res *= b;}b *= b;n >>= 1;}return res;}bool operator==(ModInt that) const { return x == that.get(); }bool operator!=(ModInt that) const { return x != that.get(); }ModInt operator-() const { return x == 0 ? 0 : ModInt(mod-x); }};template<long long MOD> ostream& operator<< (ostream& os, const ModInt<MOD>& m) { os << m.get(); return os; }template<long long MOD> istream& operator>> (istream& is, ModInt<MOD>& m){ long long n; is >> n; m = n; return is;}typedef ModInt<1000000007> mint;class ConvQuery {vector<mint> fac;vector<mint> facinv;public:ConvQuery(int n) {fac = vector<mint>(n+1);facinv = vector<mint>(n+1);fac[0] = 1;facinv[0] = 1;for(int i = 0; i < n; ++i) {fac[i+1] = fac[i]*(i+1);facinv[i+1] = fac[i+1].inverse();}}mint operator()(int n, int m) {if(n >= 0 and 0 <= m and m <= n) return fac[n]*facinv[n-m]*facinv[m];else return 0;}};const string fs = "1419141161419141251419141161419141";LL naive(LL l, LL r) {LL res = 0;FOR(i, l, r) {res += fs[i] - '0';}return res;}int main(){ios_init();LL k, l, r;while(cin >> k >> l >> r) {l--;vector<LL> fl, nl, fn, nn;vector<mint> fm, nm;fl.push_back(0);nl.push_back(0);fn.push_back(0);nn.push_back(0);fm.push_back(1);nm.push_back(1);auto nlen = [&](LL n) -> int {int res = 0;while(n != 0) {res++;n /= 10;}return res;};auto dsum = [&](LL n) -> LL {LL res = 0;while(n != 0) {if(n % 10 == 0) {res += 10;} else {res += n % 10;}n /= 10;}return res;};auto dmul = [&](LL n) -> mint {mint res = 1;while(n != 0) {if(n % 10 == 0) {res *= 10;} else {res *= n % 10;}n /= 10;}return res;};while(fl.back() < r) {int l = nlen(SZ(fl) * SZ(fl));nl.push_back(l);fl.push_back(l + 2 * fl.back());LL ds = dsum(SZ(fn) * SZ(fn));fn.push_back(ds + 2 * fn.back());nn.push_back(ds);mint dm = dmul(SZ(fm) * SZ(fm));fm.push_back(dm * fm.back() * fm.back());nm.push_back(dm);}if(SZ(fl) - 1 > k) {cout << -1 << endl;continue;}function<LL(LL, int)> get_sum = [&](LL x, int i) -> LL {LL m0 = (fl[i] - nl[i]) / 2;LL m1 = m0 + nl[i];if(m0 <= x && x <= m1) {LL res = 0;int ii = i * i;string sii = to_string(ii);REP(i, x - m0) {if((sii[i] - '0') == 0) {res += 10;} else {res += (sii[i] - '0');}}return res + fn[i - 1];} else if(m1 < x) {return fn[i - 1] + nn[i] + get_sum(x - m1, i - 1);} else {return get_sum(x, i - 1);}};function<mint(LL, int)> get_mul = [&](LL x, int i) -> mint {LL m0 = (fl[i] - nl[i]) / 2;LL m1 = m0 + nl[i];if(m0 <= x && x <= m1) {mint res = 1;int ii = i * i;string sii = to_string(ii);REP(i, x - m0) {if((sii[i] - '0') == 0) {res *= 10;} else {res *= (sii[i] - '0');}}return res * fm[i - 1];} else if(m1 < x) {return fm[i - 1] * nm[i] * get_mul(x - m1, i - 1);} else {return get_mul(x, i - 1);}};// dpite(ALL(fl));// dpite(ALL(nl));dpite(ALL(fm));dpite(ALL(nm));// DEBUG(get_sum(r, SZ(fl) - 1) );// DEBUG(get_sum(l, SZ(fl) - 1) );cout << get_sum(r, SZ(fl) - 1) - get_sum(l, SZ(fl) - 1) <<' ' << get_mul(r, SZ(fl) - 1) / get_mul(l, SZ(fl) - 1) << endl;// REP(l, SZ(fs) + 1) FOR(r, l + 1, SZ(fs) + 1) {// // DEBUG(111);// if( get_sum(r, SZ(fl) - 1) - get_sum(l, SZ(fl) - 1) != naive(l, r)) {// DEBUG(l); DEBUG(r);// }// }}return 0;}