#1021942 (C++23) No.2934 Digit Sum

提出ソース

結果

問題	No.2934 Digit Sum
ユーザー	Pedro Vinicius
提出日時	2024-10-23 13:04:22
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	10,208 bytes
コンパイル時間	6,266 ms
コンパイル使用メモリ	285,068 KB
実行使用メモリ	13,636 KB
最終ジャッジ日時	2024-10-23 13:04:32
合計ジャッジ時間	9,865 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,636 KB
testcase_01	AC	13 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	3 ms 6,824 KB
testcase_07	AC	3 ms 6,816 KB
testcase_08	AC	3 ms 6,820 KB
testcase_09	TLE	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define all(x) x.begin(), x.end()

using namespace __gnu_pbds; using namespace std;

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T, null_type , less_equal<T> , rb_tree_tag , tree_order_statistics_node_update>; typedef long long ll;  typedef pair<int, int> ii;  typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi; 
const ll oo = 1987654321987654321;

template<class It> void db(It b, It e) { for (auto it = b; it != e; it++) cout << *it << ' '; cout<< endl; } template<typename A> istream& operator>>(istream& fin, vector<A>& v) { for (auto it = v.begin(); it != v.end(); ++it) fin >> *it; return fin; } template<typename A, typename B> istream& operator>>(istream& fin, pair<A, B>& p){ fin >> p.first >> p.second; return fin; } template<typename T> void chmin(T &a, T b){ a = min(a, b); } template<typename T> void chmax(T &a, T b){ a = max(a, b); } template <typename T, typename S> ostream& operator<<(ostream& os, const pair<T, S>& v) { os << "(" << v.first << "," << v.second << ")"; return os; }

// Big Integer
//
// Complexidades: (para n digitos)
// Soma, subtracao, comparacao - O(n)
// Multiplicacao - O(n log(n))
// Divisao, resto - O(n^2)

struct bint {
	static const int BASE = 1e9;
	vector<int> v;
	bool neg;

	bint() : neg(0) {}
	bint(int val) : bint() { *this = val; }
	bint(long long val) : bint() { *this = val; }

	void trim() {
		while (v.size() and v.back() == 0) v.pop_back();
		if (!v.size()) neg = 0;
	}

	// converter de/para string | cin/cout
	bint(const char* s) : bint() { from_string(string(s)); }
	bint(const string& s) : bint() { from_string(s); }
	void from_string(const string& s) {
		v.clear(), neg = 0;
		int ini = 0;
		while (ini < s.size() and (s[ini] == '-' or s[ini] == '+' or s[ini] == '0'))
			if (s[ini++] == '-') neg = 1;
		for (int i = s.size()-1; i >= ini; i -= 9) {
			int at = 0;
			for (int j = max(ini, i - 8); j <= i; j++) at = 10*at + (s[j]-'0');
			v.push_back(at);
		}
		if (!v.size()) neg = 0;
	}
	string to_string() const {
		if (!v.size()) return "0";
		string ret;
		if (neg) ret += '-';
		for (int i = v.size()-1; i >= 0; i--) {
			string at = ::to_string(v[i]);
			int add = 9 - at.size();
			if (i+1 < v.size()) for (int j = 0; j < add; j++) ret += '0';
			ret += at;
		}
		return ret;
	}
	friend istream& operator>>(istream& in, bint& val) {
		string s; in >> s;
		val = s;
		return in;
	}
	friend ostream& operator<<(ostream& out, const bint& val) {
		string s = val.to_string();
		out << s;
		return out;
	}

	// operators
	friend bint abs(bint val) {
		val.neg = 0;
		return val;
	}
	friend bint operator-(bint val) {
		if (val != 0) val.neg ^= 1;
		return val;
	}
	bint& operator=(const bint& val) { v = val.v, neg = val.neg; return *this; }
	bint& operator=(long long val) {
		v.clear(), neg = 0;
		if (val < 0) neg = 1, val *= -1;
		for (; val; val /= BASE) v.push_back(val % BASE);
		return *this;
	}
	int cmp(const bint& r) const { // menor: -1 | igual: 0 | maior: 1
		if (neg != r.neg) return neg ? -1 : 1;
		if (v.size() != r.v.size()) {
			int ret = v.size() < r.v.size() ? -1 : 1;
			return neg ? -ret : ret;
		}
		for (int i = int(v.size())-1; i >= 0; i--) {
			if (v[i] != r.v[i]) {
				int ret = v[i] < r.v[i] ? -1 : 1;
				return neg ? -ret : ret;
			}
		}
		return 0;
	}
	friend bool operator<(const bint& l, const bint& r) { return l.cmp(r) == -1; }
	friend bool operator>(const bint& l, const bint& r) { return l.cmp(r) == 1; }
	friend bool operator<=(const bint& l, const bint& r) { return l.cmp(r) <= 0; }
	friend bool operator>=(const bint& l, const bint& r) { return l.cmp(r) >= 0; }
	friend bool operator==(const bint& l, const bint& r) { return l.cmp(r) == 0; }
	friend bool operator!=(const bint& l, const bint& r) { return l.cmp(r) != 0; }

	bint& operator +=(const bint& r) {
		if (!r.v.size()) return *this;
		if (neg != r.neg) return *this -= -r;
		for (int i = 0, c = 0; i < r.v.size() or c; i++) {
			if (i == v.size()) v.push_back(0);
			v[i] += c + (i < r.v.size() ? r.v[i] : 0);
			if ((c = v[i] >= BASE)) v[i] -= BASE;
		}
		return *this;
	}
	friend bint operator+(bint a, const bint& b) { return a += b; }
	bint& operator -=(const bint& r) {
		if (!r.v.size()) return *this;
		if (neg != r.neg) return *this += -r;
		if ((!neg and *this < r) or (neg and r < *this)) {
			*this = r - *this;
			neg ^= 1;
			return *this;
		}
		for (int i = 0, c = 0; i < r.v.size() or c; i++) {
			v[i] -= c + (i < r.v.size() ? r.v[i] : 0);
			if ((c = v[i] < 0)) v[i] += BASE;
		}
		trim();
		return *this;
	}
	friend bint operator-(bint a, const bint& b) { return a -= b; }

	// operators de * / %
	bint& operator *=(int val) {
		if (val < 0) val *= -1, neg ^= 1;
		for (int i = 0, c = 0; i < v.size() or c; i++) {
			if (i == v.size()) v.push_back(0);
			long long at = (long long) v[i] * val + c;
			v[i] = at % BASE;
			c = at / BASE;
		}
		trim();
		return *this;
	}
	friend bint operator *(bint a, int b) { return a *= b; }
	friend bint operator *(int a, bint b) { return b *= a; }
	using cplx = complex<double>;
	void fft(vector<cplx>& a, bool f, int N, vector<int>& rev) const {
		for (int i = 0; i < N; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
		vector<cplx> roots(N);
		for (int n = 2; n <= N; n *= 2) {
			const static double PI = acos(-1);
			for (int i = 0; i < n/2; i++) {
				double alpha = (2*PI*i)/n;
				if (f) alpha = -alpha;
				roots[i] = cplx(cos(alpha), sin(alpha));
			}
			for (int pos = 0; pos < N; pos += n)
				for (int l = pos, r = pos+n/2, m = 0; m < n/2; l++, r++, m++) {
					auto t = roots[m]*a[r];
					a[r] = a[l] - t;
					a[l] = a[l] + t;
				}
		}
		if (!f) return;
		auto invN = cplx(1)/cplx(N);
		for (int i = 0; i < N; i++) a[i] *= invN;
	}
	vector<long long> convolution(const vector<int>& a, const vector<int>& b) const {
		vector<cplx> l(a.begin(), a.end()), r(b.begin(), b.end());
		int ln = l.size(), rn = r.size(), N = ln+rn+1, n = 1, log_n = 0;
		while (n <= N) n <<= 1, log_n++;
		vector<int> rev(n);
		for (int i = 0; i < n; i++) {
			rev[i] = 0;
			for (int j = 0; j < log_n; j++) if (i>>j&1)
				rev[i] |= 1 << (log_n-1-j);
		}
		l.resize(n), r.resize(n);
		fft(l, false, n, rev), fft(r, false, n, rev);
		for (int i = 0; i < n; i++) l[i] *= r[i];
		fft(l, true, n, rev);
		vector<long long> ret;
		for (auto& i : l) ret.push_back(round(i.real()));
		return ret;
	}
	vector<int> convert_base(const vector<int>& a, int from, int to) const {
		static vector<long long> pot(10, 1);
		if (pot[1] == 1) for (int i = 1; i < 10; i++) pot[i] = 10*pot[i-1];
		vector<int> ret;
		long long at = 0;
		int digits = 0;
		for (int i : a) {
			at += i * pot[digits];
			digits += from;
			while (digits >= to) {
				ret.push_back(at % pot[to]);
				at /= pot[to];
				digits -= to;
			}
		}
		ret.push_back(at);
		while (ret.size() and ret.back() == 0) ret.pop_back();
		return ret;
	}
	bint operator*(const bint& r) const { // O(n log(n))
		bint ret;
		ret.neg = neg ^ r.neg;
		auto conv = convolution(convert_base(v, 9, 4), convert_base(r.v, 9, 4));
		long long c = 0;
		for (auto i : conv) {
			long long at = i+c;
			ret.v.push_back(at % 10000);
			c = at / 10000;
		}
		for (; c; c /= 10000) ret.v.push_back(c%10000);
		ret.v = convert_base(ret.v, 4, 9);
		if (!ret.v.size()) ret.neg = 0;
		return ret;
	}
	bint& operator*=(const bint& r) { return *this = *this * r; };
	bint& operator/=(int val) {
		if (val < 0) neg ^= 1, val *= -1;
		for (int i = int(v.size())-1, c = 0; i >= 0; i--) {
			long long at = v[i] + c * (long long) BASE;
			v[i] = at / val;
			c = at % val;
		}
		trim();
		return *this;
	}
	friend bint operator/(bint a, int b) { return a /= b; }
	int operator %=(int val) {
		if (val < 0) val *= -1;
		long long at = 0;
		for (int i = int(v.size())-1; i >= 0; i--)
			at = (BASE * at + v[i]) % val;
		if (neg) at *= -1;
		return at;
	}
	friend int operator%(bint a, int b) { return a %= b; }
	friend pair<bint, bint> divmod(const bint& a_, const bint& b_) { // O(n^2)
		if (a_ == 0) return {0, 0};
		int norm = BASE / (b_.v.back() + 1);
		bint a = abs(a_) * norm;
		bint b = abs(b_) * norm;
		bint q, r;
		for (int i = a.v.size() - 1; i >= 0; i--) {
			r *= BASE, r += a.v[i];
			long long upper = b.v.size() < r.v.size() ? r.v[b.v.size()] : 0;
			int lower = b.v.size() - 1 < r.v.size() ? r.v[b.v.size() - 1] : 0;
			int d = (upper * BASE + lower) / b.v.back();
			r -= b*d;
			while (r < 0) r += b, d--; // roda O(1) vezes
			q.v.push_back(d);
		}
		reverse(q.v.begin(), q.v.end());
		q.neg = a_.neg ^ b_.neg;
		r.neg = a_.neg;
		q.trim(), r.trim();
		return {q, r / norm};
	}
	bint operator/(const bint& val) { return divmod(*this, val).first; }
	bint& operator/=(const bint& val) { return *this = *this / val; }
	bint operator%(const bint& val) { return divmod(*this, val).second; }
	bint& operator%=(const bint& val) { return *this = *this % val; }
};

ll memo[35][2][35 * 9 + 5];

vi num2v(bint n) {
  vi retval;
  if (n == 0) retval.push_back(0);
  while (n > 0) {
    retval.push_back(n % 10);
    n /= 10;
  }
  reverse(all(retval));
  return retval;
}

ll n;

ll dp(vi &digitos, int i = 0, bool empatado = true, int x = 0) {
  if (i == digitos.size()) {
    return 1;
  }
  ll &ans = memo[i][empatado][x];
  if (ans != -1) return ans;
  ans = 0;
  int r = empatado ? digitos[i] : 9;
  for (int val = 0; val <= r; val++) {
    bool new_empatado = empatado && val == r;
    if (x + val <= n){
        ans += dp(digitos, i + 1, new_empatado, x + val);
    }
  }
  return ans;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    ll k;
    cin >> n >> k;
    ++k;
    chmin(n, (ll)300);
    auto good = [&](bint x){
        vi digitos = num2v(x);
        memset(memo, -1, sizeof(memo));
        return dp(digitos) >= k;
    };
    bint l = 0;
    bint r = 1;
    while (!good(r)) r *= 2;
    while (r - l > 1){
        bint mid = l + (r - l)/2;
        if (good(mid)) r = mid;
        else l = mid;
    }
    cout << r << "\n";
}

yukicoder

結果

テストケース

ソースコード