QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302272#7954. Special Numbersmshcherba#WA 347ms13664kbC++202.1kb2024-01-10 18:19:562024-01-10 18:19:56

Judging History

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

  • [2024-01-10 18:19:56]
  • 评测
  • 测评结果:WA
  • 用时:347ms
  • 内存:13664kb
  • [2024-01-10 18:19:56]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1'000'000'007;
const int p[4] = {2, 3, 5, 7};

void updAdd(int& a, int b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}

void updSub(int& a, int b)
{
	a -= b;
	if (a < 0)
		a += mod;
}

int alpha[4];
array<int, 4> bet[10];

int f(LL n)
{
	VI digits;
	while (n > 0)
	{
		digits.PB(n % 10);
		n /= 10;
	}
	reverse(ALL(digits));
	map<array<int, 4>, int> dp[2][2];
	FOR(d, 1, digits[0] + 1)
	{
		dp[d == digits[0]][0][bet[d]] = 1;
	}
	FOR(i, 1, SZ(digits))
	{
		map<array<int, 4>, int> ndp[2][2];
		FOR(d, 1, 10)
		{
			ndp[0][0][bet[d]] = 1;
		}
		FOR(v, 0, 2)
		{
			FOR(wz, 0, 2)
			{
				for (const auto& [be, cnt] : dp[v][wz])
				{
					FOR(d, 0, 10)
					{
						if (v && d > digits[i])
							break;
						array<int, 4> nbe = be;
						FOR(j, 0, 4)
							nbe[j] += bet[d][j];
						updAdd(ndp[v && d == digits[i]][wz || d == 0][nbe], cnt);
					}
				}
			}
		}
		FOR(v, 0, 2)
			FOR(wz, 0, 2)
				dp[v][wz] = ndp[v][wz];
	}
	int res = 0;
	FOR(v, 0, 2)
	{
		FOR(wz, 0, 2)
		{
			for (const auto& [be, cnt] : dp[v][wz])
			{
				bool ok = true;
				FOR(j, 0, 4)
					ok &= be[j] >= alpha[j];
				if (wz || ok)
				{
					updAdd(res, cnt);
				}
			}
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	LL k, l, r;
	cin >> k >> l >> r;
	FOR(i, 0, 4)
	{
		while (k % p[i] == 0)
		{
			k /= p[i];
			alpha[i]++;
		}
	}
	FOR(d, 1, 10)
	{
		int cur = d;
		FOR(i, 0, 4)
		{
			while (cur % p[i] == 0)
			{
				cur /= p[i];
				bet[d][i]++;
			}
		}
	}
	int ans = f(r);
	if (l > 1)
		updSub(ans, f(l - 1));
	cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

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

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

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

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

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

input:

1 100 100000

output:

99901

result:

ok single line: '99901'

Test #5:

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

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #6:

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

input:

10 800 43021

output:

23570

result:

ok single line: '23570'

Test #7:

score: -100
Wrong Answer
time: 347ms
memory: 13664kb

input:

1125899906842624 1 100000000000000000000

output:

566570801

result:

wrong answer 1st lines differ - expected: '555058180', found: '566570801'