QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#5861#555. 代码Qingyu100 ✓62ms12816kbC++172.7kb2021-01-26 00:20:482021-12-19 07:04:59

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 07:04:59]
  • Judged
  • Verdict: 100
  • Time: 62ms
  • Memory: 12816kb
  • [2021-01-26 00:20:48]
  • Submitted

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;
}

详细

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'