QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724886#7954. Special Numbersgugugaga#WA 1ms3788kbC++2010.8kb2024-11-08 15:27:102024-11-08 15:27:16

Judging History

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

  • [2024-11-08 15:27:16]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3788kb
查看
  • [2024-11-08 15:27:10]
  • 提交

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;

void process(void) {
	long long k, l, r; cin >> k >> l >> r;
	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 = [&] (long long 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);
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3600kb

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

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

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

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

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

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

input:

1 100 100000

output:

99901

result:

ok single line: '99901'

Test #5:

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

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #6:

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

input:

10 800 43021

output:

23570

result:

ok single line: '23570'

Test #7:

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

input:

1125899906842624 1 100000000000000000000

output:

566570801

result:

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

服务器时间: 2024-12-03 06:59:06 | 开源项目