QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724920#7954. Special Numbersgugugaga#WA 14ms9012kbC++2011.0kb2024-11-08 15:34:012024-11-08 15:34:03

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 15:34:03]
  • 评测
  • 测评结果：WA
  • 用时：14ms
  • 内存：9012kb
查看
  • [2024-11-08 15:34:01]
  • 提交

answer

/*************************************
*    author: marvinthang             *
*    created: 08.11.2024 14:07:07    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define             fi  first
#define             se  second
#define           left  ___left___
#define          right  ___right___
#define   scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define  print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
	#include "debug.h"
#else
	#define DB(...)
	#define db(...) ""
	#define debug(...)
#endif

namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {} template <class...Args> decltype(auto)operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } };
template <class Fun> decltype(auto)y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); }
template <typename T, int D> struct Vec: public vector <Vec<T, D - 1>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename ...Args> Vec(int n = 0, Args ...args): vector <Vec<T, D - 1>>(n, Vec<T, D - 1>(args...)) {} };
template <typename T> struct Vec<T, 1>: public vector<T>{ Vec(int n = 0, const T &val = T()): vector<T>(n, val) {} };
#if __cplusplus < 202002L
	template <class T> int ssize(const T &a) { return a.size(); }
#endif
}

namespace MODINT {
struct barrett {
	unsigned int _m;
	unsigned long long im;
	explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
	unsigned int umod() const { return _m; };
	unsigned int mul(unsigned int a, unsigned int b) const {
		unsigned long long z = a; z *= b;
		unsigned long long x = (unsigned long long)(((unsigned __int128) z * im) >> 64);
		unsigned long long y = x * _m;
		return (unsigned int)(z - y + (z < y ? _m : 0));
	}
};
template <class T> T invGeneral(T a, T b) {
	a %= b;
	if (!a) return b == 1 ? 0 : -1;
	T x = invGeneral(b, a);
	return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
}
template <int m, enable_if_t<1 <= m>* = nullptr>
struct static_modint {
using mint = static_modint;
public:
	static constexpr int mod() { return m; }
	static mint raw(int v) {
		mint x; x.v = v;
		return x;
	}
	static_modint(): v(0) {}
	template <class T> static_modint(T x) {
		int y;
		if (x < 0) {
			if (x < -mod()) y = x % mod();
			else y = x;
			if (y < 0) y += mod();
		} else {
			if (x < mod()) y = x;
			else y = x % mod();
		}
		v = y;
	}
	unsigned int val() const { return v; }
	unsigned int operator () () const { return v; }
	mint & operator ++ () { if (++v == umod()) v = 0; return *this; }
	mint & operator -- () { if (!v) v = umod(); --v; return *this; }
	mint operator ++ (int) { mint old = *this; ++*this; return old; }
	mint operator -- (int) { mint old = *this; --*this; return old; }
	mint operator + () { return *this; }
	mint operator - () { return raw(!v ? 0 : umod() - v); }
	mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; }
	mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; }
	mint & operator *= (const mint &rhs) {
		unsigned long long z = v; z *= rhs.v; v = z % umod();
		return *this;
	}
	mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); }
	friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
	friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
	friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
	friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
	mint pow(long long n) const {
		assert(0 <= n);
		mint res = 1, a = *this;
		for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
		return res;
	}
	mint inv() const {
		int i = invGeneral((int) v, mod());
		assert(~i);
		return i;
	}
	friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; }
	friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; }
	friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; }
	friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; }
	explicit operator bool() const { return v; }
	explicit operator int() const { return v; }
private:
	unsigned int v;
	static constexpr unsigned int umod() { return m; }
};
template <int id> struct dynamic_modint {
using mint = dynamic_modint;
public:
	static int mod() { return (int) bt.umod(); }
	static void set_mod(int m) {
		assert(1 <= m);
		bt = barrett(m);
	}
	static mint raw(int v) {
		mint x; x.v = v;
		return x;
	}
	dynamic_modint(): v(0) {}
	template <class T> dynamic_modint(T x) {
		int y;
		if (x < 0) {
			if (x < -mod()) y = x % mod();
			else y = x;
			if (y < 0) y += mod();
		} else {
			if (x < mod()) y = x;
			else y = x % mod();
		}
		v = y;
	}
	unsigned int val() const { return v; }
	unsigned int operator () () const { return v; }
	mint & operator ++ () { if (++v == umod()) v = 0; return *this; }
	mint & operator -- () { if (!v) v = umod(); --v; return *this; }
	mint operator ++ (int) { mint old = *this; ++*this; return old; }
	mint operator -- (int) { mint old = *this; --*this; return old; }
	mint operator + () { return *this; }
	mint operator - () { return raw(!v ? 0 : umod() - v); }
	mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; }
	mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; }
	mint & operator *= (const mint &rhs) {
		v = bt.mul(v, rhs.v);
		return *this;
	}
	mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); }
	friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
	friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
	friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
	friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
	mint pow(long long n) const {
		assert(0 <= n);
		mint res = 1, a = *this;
		for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
		return res;
	}
	mint inv() const {
		int i = invGeneral((int) v, mod());
		assert(~i);
		return i;
	}
	friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; }
	friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; }
	friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; }
	friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; }
	explicit operator bool() const { return v; }
	explicit operator int() const { return v; }
private:
	unsigned int v;
	static barrett bt;
	static unsigned int umod() { return bt.umod(); }
};
template <int id> barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint <-1>;
using Modular = modint1000000007;
} using namespace MODINT;

__int128 read_int128(void) {
	string s; cin >> s;
	__int128 res = 0;
	for (char c : s) {
		res = res * 10 + c - '0';
	}
	return res;
}

void process(void) {
	long long k;
	cin >> k;
	__int128 l = read_int128(), r = read_int128();
	int cnt_2 = 0, cnt_3 = 0, cnt_5 = 0, cnt_7 = 0;
	while (k % 2 == 0) k /= 2, ++cnt_2;
	while (k % 3 == 0) k /= 3, ++cnt_3;
	while (k % 5 == 0) k /= 5, ++cnt_5;
	while (k % 7 == 0) k /= 7, ++cnt_7;
	if (k != 1) {
		cout << "0\n";
		return;
	}
	Vec <int, 2> f(10, 4);
	f[0][0] = cnt_2;
	f[0][1] = cnt_3;
	f[0][2] = cnt_5;
	f[0][3] = cnt_7;
	for (int i = 1; i < 10; ++i) {
		int d = i;
		while (d % 2 == 0) d /= 2, ++f[i][0];
		while (d % 3 == 0) d /= 3, ++f[i][1];
		while (d % 5 == 0) d /= 5, ++f[i][2];
		while (d % 7 == 0) d /= 7, ++f[i][3];
	}
	auto calc = [&] (__int128 r) -> Modular {
		if (!r) return 0;
		vector <int> digits;
		while (r) {
			digits.push_back(r % 10);
			r /= 10;
		}
		int n = ssize(digits);
		Vec <Modular, 6> dp(n + 1, cnt_2 + 1, cnt_3 + 1, cnt_5 + 1, cnt_7 + 1, 2);
		dp[0][0][0][0][0][1] = 1;
		Modular res = 0;
		for (int i = 0; i < n; ++i) {
			for (int c2 = 0; c2 <= cnt_2; ++c2) {
				for (int c3 = 0; c3 <= cnt_3; ++c3) {
					for (int c5 = 0; c5 <= cnt_5; ++c5) {
						for (int c7 = 0; c7 <= cnt_7; ++c7) {
							for (int le = 0; le < 2; ++le) {
								if (!dp[i][c2][c3][c5][c7][le]) continue;
								for (int d = 0; d < 10; ++d) {
									int nc2 = min(cnt_2, c2 + f[d][0]);
									int nc3 = min(cnt_3, c3 + f[d][1]);
									int nc5 = min(cnt_5, c5 + f[d][2]);
									int nc7 = min(cnt_7, c7 + f[d][3]);
									int nle = d < digits[i] || (d == digits[i] && le);
									dp[i + 1][nc2][nc3][nc5][nc7][nle] += dp[i][c2][c3][c5][c7][le];
									if (d && (i + 1 < n || nle) && nc2 == cnt_2 && nc3 == cnt_3 && nc5 == cnt_5 && nc7 == cnt_7) {
										res += dp[i][c2][c3][c5][c7][le];
									}
								}
							}
						}
					}
				}
			}
		}
		return res;
	};
	cout << calc(r) - calc(l - 1) << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	file("test");
	// int t; cin >> t; while (t--)
	process();
	return (0^0);
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1 100 100000

output:

99901

result:

ok single line: '99901'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

10 800 43021

output:

23570

result:

ok single line: '23570'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

1125899906842624 1 100000000000000000000

output:

555058180

result:

ok single line: '555058180'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

187500000 5941554024261918062 17356601866920567143

output:

679191360

result:

ok single line: '679191360'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

1555848 157165614890794026 49792374427566422833

output:

588832126

result:

ok single line: '588832126'

Test #10:

score: 0
Accepted
time: 10ms
memory: 6816kb

input:

53814924637488000 8378901287491856069 46225409092942057365

output:

964965504

result:

ok single line: '964965504'

Test #11:

score: 0
Accepted
time: 11ms
memory: 9012kb

input:

11814720750000000 8152927138245188051 35351923956338524619

output:

183963359

result:

ok single line: '183963359'

Test #12:

score: 0
Accepted
time: 5ms
memory: 5180kb

input:

6453888000000 4334845344448208535 35982793193772682339

output:

570114022

result:

ok single line: '570114022'

Test #13:

score: 0
Accepted
time: 7ms
memory: 6020kb

input:

90071357282285400 7893548167754114409 27099084703937108974

output:

869822186

result:

ok single line: '869822186'

Test #14:

score: 0
Accepted
time: 7ms
memory: 6248kb

input:

45571065750000 177160749596350425 98884377930460959454

output:

607698665

result:

ok single line: '607698665'

Test #15:

score: 0
Accepted
time: 6ms
memory: 5908kb

input:

1128443962982400 6338876482181492537 40931938533793596007

output:

881168270

result:

ok single line: '881168270'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 3ms
memory: 4864kb

input:

1412793457031250 2410155470167050095 99063185266833009818

output:

399813226

result:

ok single line: '399813226'

Test #18:

score: 0
Accepted
time: 10ms
memory: 7360kb

input:

67722117120000 8909573534349989418 73129289758235281558

output:

898227227

result:

ok single line: '898227227'

Test #19:

score: 0
Accepted
time: 4ms
memory: 4692kb

input:

472055808000 6809917603531307093 27494416416722163137

output:

379198478

result:

ok single line: '379198478'

Test #20:

score: 0
Accepted
time: 4ms
memory: 5104kb

input:

19353600000 8687492345912514346 24058039408337150852

output:

250715555

result:

ok single line: '250715555'

Test #21:

score: 0
Accepted
time: 0ms
memory: 4280kb

input:

47855420020225440 6150828649270625443 84863934988301168136

output:

665186711

result:

ok single line: '665186711'

Test #22:

score: 0
Accepted
time: 2ms
memory: 4320kb

input:

1382400000 9545797804645162278 70441077437727026904

output:

278230087

result:

ok single line: '278230087'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

816293376 2952089614708276156 10939708785225040670

output:

120954190

result:

ok single line: '120954190'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

4185097875 1348426133484952253 56617823359794500344

output:

773995224

result:

ok single line: '773995224'

Test #25:

score: 0
Accepted
time: 3ms
memory: 4488kb

input:

5828945117184 7777082394971366991 63470232991138132969

output:

678496908

result:

ok single line: '678496908'

Test #26:

score: 0
Accepted
time: 3ms
memory: 4408kb

input:

16184770560 3869053219872876321 94590086601168840932

output:

168181821

result:

ok single line: '168181821'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

2 1 12

output:

6

result:

ok single line: '6'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

30146484375 290228705524339176 51853415145287716863

output:

229436627

result:

ok single line: '229436627'

Test #29:

score: 0
Accepted
time: 5ms
memory: 5268kb

input:

2072513819443200 3726664558969607832 42501102605103061370

output:

947952932

result:

ok single line: '947952932'

Test #30:

score: 0
Accepted
time: 14ms
memory: 8740kb

input:

9920232000000000 4602219263214498291 80783137037024823899

output:

846877519

result:

ok single line: '846877519'

Test #31:

score: 0
Accepted
time: 7ms
memory: 6576kb

input:

97200000000000000 9310820760839688870 35322929083473756214

output:

936587432

result:

ok single line: '936587432'

Test #32:

score: 0
Accepted
time: 1ms
memory: 4128kb

input:

45209390625 5752361069878044328 64635325028527078951

output:

578047592

result:

ok single line: '578047592'

Test #33:

score: 0
Accepted
time: 7ms
memory: 7284kb

input:

54442233216000 2452030574225118723 90982734056131320662

output:

417646585

result:

ok single line: '417646585'

Test #34:

score: 0
Accepted
time: 4ms
memory: 5052kb

input:

1530550080000 7431421026778839808 84825282227911272129

output:

600103842

result:

ok single line: '600103842'

Test #35:

score: 0
Accepted
time: 7ms
memory: 6152kb

input:

13765147361280 4924477486471254843 10002324705150566233

output:

951883713

result:

ok single line: '951883713'

Test #36:

score: 0
Accepted
time: 3ms
memory: 6028kb

input:

59825698242187500 6303744363677706767 91410210495502213963

output:

774734375

result:

ok single line: '774734375'

Test #37:

score: 0
Accepted
time: 8ms
memory: 6184kb

input:

110658879959040 2133591391458550040 48494371567095341228

output:

103505650

result:

ok single line: '103505650'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

1 3 100

output:

98

result:

ok single line: '98'

Test #39:

score: 0
Accepted
time: 7ms
memory: 5964kb

input:

3160365465600 8968721517098518892 78444481529635953131

output:

364620926

result:

ok single line: '364620926'

Test #40:

score: -100
Wrong Answer
time: 0ms
memory: 3656kb

input:

54838448056132899 4242999884713464056 92948071680698209741

output:

0

result:

wrong answer 1st lines differ - expected: '922087167', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-03 04:13:14 | OpenSource Project