胡闹 回文

题目大意

求$[0,n]$中有几个$n\le10^6$位数(考虑前导$0$)满足如下情况:

  1. 这个数是一个回文数。
  2. 这个数奇数位上的和等于偶数位上的和。

解析

假设$n$是一个偶数,那么答案显然是$10^\frac{n}{2}$对吧。

然后假设$n$是一个奇数。

$\mathcal{O(n^2)}$ 的$dp$做法

我们可以设dp[i][j]​为长度为i(不考虑前导$0$),奇数位与偶数位的差为j的数的总数。

这个随便转移一下就好了。

但是这可能出现负数下标,这很难受,有两个解决方案:

  1. #define Dp(i, j) dp[i][j+Min_Value]
  2. __gnu_pbds::gp_hash_table<int, int>

但是如果你傻逼如我(不可能)用了这种东西map<int, int>

那么恭喜你,获得一个$log$的$debuff$并且挂成暴力。

正确的复杂度

这看上去是一个容斥。

然后我们考虑怎么个容斥法。

对于形如$n=4k+1$的数的话,我们推一推式子:
$$
\begin{align}
2\times(x_1 + x_3 + · · · + x_{2k−1}) + x_{2k+1} &= 2 \times (x_2 + x_4 + · · · + x_{2k})\\
x_2+x_4+· · ·+x_{2k}+(9−x_1)+(9−x_2)+· · ·+(9−x_{2k−1})&=9k+\frac{x_{2k+1}}{2}
\end{align}
$$
那么我们考虑枚举一下$\frac{x_{2k+1}}{2}$,这就变成了一个容斥然后隔板法(别问我为什么,WO YE BU HUI)。

对于形如$n=4k+3$的样子,多考虑一个数就可以了(WO YE BU HUI)

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
63
64
#define  REP(i, s, e) for (register int i = s; i <= e; i++)
#define DREP(i, s, e) for (register int i = s; i >= e; i--)

#include <bits/extc++.h>
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e7 + 10, MOD = 1e9 + 7;

inline int power_pow(int a, int b)
{
int ans(1), base(a);
while (b)
{
if (b & 1) ans = ans * base % MOD;
base = base * base % MOD;
b >>= 1;
}
return (ans + MOD) % MOD;
}
#define inv(x) power_pow(x, MOD - 2)
int n;
int fac[maxn], Inv[maxn];
inline int C(int n, int m) {return n < m || m < 0 ? 0 : fac[n] * Inv[n-m] % MOD * Inv[m] % MOD;}

inline int solve(int S, int n)
{
int res(0), cur(-1);
REP(i, 0, n) res += (cur *= -1) * C(n, i) * C(S - i * 10 + n - 1, n - 1) % MOD, res %= MOD;
return (res + MOD) % MOD;
}
__gnu_pbds::gp_hash_table <int,int> cnt;
__gnu_pbds::gp_hash_table <int,int> :: iterator it;

signed main()
{
#ifndef ONLINE_JUDGE
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif
Inv[0] = fac[0] = 1;
REP(i, 1, 10000000) fac[i] = fac[i-1] * i % MOD;
Inv[10000000] = inv(fac[10000000]);
DREP(i, 9999999, 1) Inv[i] = Inv[i+1] * (i+1) % MOD;
int T;cin >> T;
while (T--)
{
scanf("%lld", &n);
int ans = 0;
if (n % 2 == 0) ans = power_pow(10, n >> 1);
else if (n == 1) ans = 1;
else if (n == 3) ans = 5;
else if (n % 4 == 1) REP(i, 0, 4) ans += solve(i + 9 * (n >> 2), n >> 1) % MOD, ans %= MOD;
else
{
cnt.clear();
REP(i, 0, 4) REP(j, 0, 9) cnt[i-j]++;
for (it = cnt.begin(); it != cnt.end(); it++)
ans += solve(it -> first + 9 * (n >> 2), (n >> 1) - 1) * it -> second % MOD, ans %= MOD;
}
printf("%lld\n", ans);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×