QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694230 | #6522. Digit Mode | Shuishui# | WA | 2ms | 3712kb | C++14 | 2.8kb | 2024-10-31 17:31:02 | 2024-10-31 17:31:02 |
Judging History
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'