Description
给你一个 $n ^ 2$ 位的数 $k$ ，请你求出有多少个整数 $x \in [1, k]$ ，满足 $x$ 翻转或大于 $k$ 或翻转后大于等于它自己。 例如 123 翻转后为 321 。
Solution
对于这类问题，我们考虑使用 数位 DP 来解决。
正难则反，考虑求出翻转后小于等于 $k$ ， 小于 它自己的数的个数。
所以如果设 $f(i)$ 表示 $i$ 翻转后的结果，那么答案 $ans=$
于是我们可以想到设 $f(i, p=0/1, q=0/1)$ 表示当前做到第 $i$ 位， $p$ 表示当前 小于/等于 $k$ 的前 $i$ 位，$q$ 表示将前 $i$ 位翻转后得到的后 $i$ 位 小于等于/大于 $k$ 的后 $i$ 位。
于是我们就得到了一个时间复杂度为 $O(n ^ 2)$ 的做法，具体细节见代码部分。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <cstdio>
#define maxN 1000010
#define mod 1000000007
long long f[maxN][2][2], a[maxN];
int main ()
{
long long ans = 0, n = 0;
scanf("%lld", &n);
n *= n;
for(long long i = 1;i <= n; i++)
{
scanf("%1lld", &a[i]);
ans = ans * 10 + a[i];
ans %= mod;
}
f[0][1][0] = 1;
for(long long i = 0;i <= n - 1; i++)
{
for(long long p = 0;p <= 1; p++)
{
for(long long q = 0;q <= 1; q++)
{
for(long long k = 0;k <= 9; k++)
{
if(p && k > a[i + 1])
{
break;
}
long long pp = 0, qq = 0;
if(p)
{
if(k == a[i + 1])
{
pp = 1;
}
}
if(!q)
{
if(k > a[n - i])
{
qq = 1;
}
}
else
{
if(k >= a[n - i])
{
qq = 1;
}
}
f[i + 1][pp][qq] += f[i][p][q];
f[i + 1][pp][qq] %= mod;
}
}
}
}
long long da1 = (f[n][0][0] + f[n][1][0]) % mod;
long long da2 = ((f[n / 2][0][0] + f[n / 2][0][1]) % mod + f[n / 2][1][0]) % mod;
ans = (ans + mod - ((da1 + mod - da2) % mod * 500000004LL % mod)) % mod;
printf("%lld", ans);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <cstdio>
#define maxN 1000010
#define mod 1000000007
long long f[maxN][2][2], a[maxN];
int main ()
{
long long ans = 0, n = 0;
scanf("%lld", &n);
for(long long i = 1;i <= n * n; i++)
{
scanf("%1lld", &a[i]);
(ans = ans * 10 + a[i]) %= mod;
}
f[0][1][0] = 1;
for(long long i = 0;i < n * n; i++)
{
for(long long p = 0;p <= 1; p++)
{
for(long long q = 0;q <= 1; q++)
{
for(long long k = 0;k <= 9; k++)
{
if(!(p & (k > a[i + 1])))
{
(f[i + 1][p & (k == a[i + 1])][((!q) & (k > a[n * n - i])) | (q & (k >= a[n * n - i]))] += f[i][p][q]) %= mod;
}
}
}
}
}
ans = (ans + mod - (((f[n * n][0][0] + f[n * n][1][0]) % mod + mod - ((f[n * n / 2][0][0] + f[n * n / 2][0][1]) % mod + f[n * n / 2][1][0]) % mod) % mod * 500000004LL % mod)) % mod;
printf("%lld", ans);
return 0;
}
|