QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#5861 | #555. 代码 | Qingyu | 100 ✓ | 62ms | 12816kb | C++17 | 2.7kb | 2021-01-26 00:20:48 | 2021-12-19 07:04:59 |
Judging History
answer
#include<cassert>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105, MOD = 1000000007, L = 6, DELTA = N;
int n, k;
int cnt[L], arbi[N], noLoop[N][N << 1];
#define div DIV
vector<int> div[N];
int dp[N][N << 1][N];
void init() {
for (int i = 1; i < N; ++i) {
div[i].clear();
for (int j = 1; j < i; ++j) {
if (i % j == 0) {
div[i].push_back(j);
}
}
}
memset(cnt, 0, sizeof(cnt));
cnt[1] = 2;
for (int i = 2, d = 1; k >= d; ++i, d *= 10) {
if (k >= d * 10) {
cnt[i] = d * 9;
} else {
cnt[i] = k - d + 1;
}
}
arbi[0] = 1;
arbi[1] = 2;
for (int i = 2; i < N; ++i) {
for (int j = 1; j < L && j <= i; ++j) {
(arbi[i] += (long long)cnt[j] * arbi[i - j] % MOD) %= MOD;
}
for (int l = 2; l <= i; ++l) {
(arbi[i] += (long long)arbi[l - 2] * arbi[i - l] % MOD) %= MOD;
}
}
memset(noLoop, 0, sizeof(noLoop));
noLoop[0][DELTA] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = -i + DELTA; j <= i + DELTA; ++j) {
noLoop[i][j] = (noLoop[i - 1][j + 1] + noLoop[i - 1][j - 1]) % MOD;
for (int k = 2; k < L && k <= i; ++k) {
(noLoop[i][j] += (long long)noLoop[i - k][j] * cnt[k] % MOD) %= MOD;
}
}
}
}
int calc() {
memset(dp, 0, sizeof(dp));
dp[0][DELTA][0] = 1;
for (int i = 0; i < n; ++i) {
for (int jj = -i; jj <= i; ++jj) {
int j = jj + DELTA;
for (int k = 0; k <= i; ++k) {
if (dp[i][j][k] == 0) {
continue;
}
if (jj == 0) {
for (int l = 2; i + l <= n; ++l) {
(dp[i + l][j][k] += (long long)dp[i][j][k] * arbi[l - 2] % MOD) %= MOD;
}
if (k) {
(dp[i + 1][j][k - 1] += dp[i][j][k]) %= MOD;
}
(dp[i + 1][j + 1][k] += dp[i][j][k]) %= MOD;
(dp[i + 1][j - 1][k] += dp[i][j][k]) %= MOD;
for (int l = 2; i + l <= n && l < L; ++l) {
(dp[i + l][j][k] += (long long)dp[i][j][k] * cnt[l] % MOD) %= MOD;
}
} else {
for (int id = 0; id < (int)div[abs(jj)].size(); ++id) {
int d = div[abs(jj)][id];
for (int l = 2; i + l <= n; ++l) {
(dp[i + l][N][k] += (long long)dp[i][j][k] * noLoop[l - 2][d + DELTA] % MOD) %= MOD;
}
}
(dp[i + 1][j][k + 1] += dp[i][j][k]) %= MOD;
(dp[i + 1][j + 1][k] += dp[i][j][k]) %= MOD;
(dp[i + 1][j - 1][k] += dp[i][j][k]) %= MOD;
for (int l = 2; i + l <= n && l < L; ++l) {
(dp[i + l][j][k] += (long long)dp[i][j][k] * cnt[l] % MOD) %= MOD;
}
}
}
}
}
int ans = 0;
for (int i = -n; i <= n; ++i) {
(ans += dp[n][i + DELTA][0]) %= MOD;
}
return ans;
}
int main() {
scanf("%d%d", &n, &k);
init();
printf("%d\n", calc());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 2ms
memory: 12716kb
input:
10 9
output:
2320540
result:
ok single line: '2320540'
Test #2:
score: 10
Accepted
time: 4ms
memory: 12716kb
input:
10 99
output:
38768740
result:
ok single line: '38768740'
Test #3:
score: 10
Accepted
time: 1ms
memory: 12740kb
input:
10 100
output:
38879818
result:
ok single line: '38879818'
Test #4:
score: 10
Accepted
time: 1ms
memory: 12784kb
input:
43 7
output:
217715835
result:
ok single line: '217715835'
Test #5:
score: 10
Accepted
time: 7ms
memory: 12704kb
input:
45 79
output:
287511486
result:
ok single line: '287511486'
Test #6:
score: 10
Accepted
time: 4ms
memory: 12760kb
input:
49 4317
output:
288237469
result:
ok single line: '288237469'
Test #7:
score: 10
Accepted
time: 60ms
memory: 12720kb
input:
100 8
output:
700817023
result:
ok single line: '700817023'
Test #8:
score: 10
Accepted
time: 50ms
memory: 12784kb
input:
98 8201
output:
655356172
result:
ok single line: '655356172'
Test #9:
score: 10
Accepted
time: 47ms
memory: 12704kb
input:
94 1777
output:
941271303
result:
ok single line: '941271303'
Test #10:
score: 10
Accepted
time: 62ms
memory: 12816kb
input:
100 9889
output:
461789726
result:
ok single line: '461789726'