QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694230#6522. Digit ModeShuishui#WA 2ms3712kbC++142.8kb2024-10-31 17:31:022024-10-31 17:31:02

Judging History

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

  • [2024-10-31 17:31:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3712kb
  • [2024-10-31 17:31:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x).size()
#define bit(x) (1ll << (x))
using ll = long long;
using db = double;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vd = vector<db>;
mt19937 mrand(time(0));

const int mod = 1e9 + 7, CN = 1002;
ll inv[CN + 8], fac[CN + 8], ifac[CN + 8];

ll C(int a, int b) {
    if (b > a || b < 0) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod; 
}

void init() {
    inv[1] = fac[0] = ifac[0] = 1;
    for (int i = 2; i <= CN; i++) 
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= CN; i++)
        fac[i] = fac[i - 1] * i % mod, ifac[i] = ifac[i - 1] * inv[i] % mod;    
}

void add(ll &a, ll b)
{
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
}

void solve(void)
{
	string s;
	cin >> s;
	vi dig;
	int n = Sz(s);
	for (int i = 0; i < n; i++)
		dig.pb(s[i] - '0');

	ll ans = 0;
	vi ad(10);

	auto calc = [&](int num)
	{
		int onum = num;
		num = n;
		vector<vll> fnum(2, vll(num + 2, vl(num + 2))), fval(2, vll(num + 2, vl(num + 2)));
		fnum[1][0][0] = 1;
		for (int i = 9; i >= 0; i--)
		{
			int u = i & 1, v = i & 1 ^ 1;

			for (int a = 0; a <= num; a++)
				for (int b = 0; b <= num; b++)
					fnum[v][a][b] = fval[v][a][b] = 0;

			for (int a = 0; a <= num; a++)
				for (int b = 0; b <= num; b++)
					for (int c = 0; c + a + ad[i] <= num && c + a <= onum; c++)
					{
						ll pnum = fnum[u][a][b], pval = fval[u][a][b];
						if (c + ad[i] > b)
						{
							add(fnum[v][a + c][c + ad[i]], pnum * C(onum - a, c) % mod);
							add(fval[v][a + c][c + ad[i]], pnum * C(onum - a, c) % mod * i % mod);
						}
						else
						{
							add(fnum[v][a + c][b], pnum * C(onum - a, c) % mod);
							add(fval[v][a + c][b], pval * C(onum - a, c) % mod);
						}
					}
		}
		// assert(fval[1][onum][0] == 0);
		for (int i = 0; i <= num; i++)
			add(ans, fval[1][onum][i]);
		
	};

	for (int i = 1; i < n; i++)
		for (int j = 1; j < 10; j++)
		{
			ad[j]++;
			calc(n - i - 1);
			ad[j]--;
		}

	for (int i = 0; i < n; i++)
	{
		for (int j = (i) ? 0 : 1; j < dig[i]; j++)
		{
			// cerr << j << "\n";
			ad[j]++;
			calc(n - i - 1);
			ad[j]--;
		}
		ad[dig[i]]++;
	}

	int mx = 0;
	for (int i = 1; i <= 9; i++)
		if (ad[i] >= mx)
			mx = i;
	add(ans, mx);
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// cout << fixed << setprecision(10);
	init();
	int T = 1;
	cin >> T;
	for (int i = 1; i <= T; i++)
	solve();

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3656kb

input:

5
9
99
999
99999
999999

output:

45
615
6570
597600
5689830

result:

ok 5 number(s): "45 615 6570 597600 5689830"

Test #2:

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

input:

34
7
48
8
76
1
97
7
5
7
7
2
89
9
4
84
46
6
73
86
78
5
3
8
9
31
24
78
7
11
45
2
65
88
6

output:

28
232
36
419
1
595
28
15
28
28
3
524
45
10
480
219
21
395
498
434
15
6
36
45
145
102
434
28
47
214
3
340
516
21

result:

wrong answer 2nd numbers differ - expected: '236', found: '232'