题目描述
For a positive integer $k$, define $d(k)$ as the sum of the digits of $k$ in its usual decimal representation. Thus $d(42) = 4+2 = 6$.
For a positive integer $n$, define $S(n)$ as the number of positive integers $k < 10^n$ with the following properties :
- $k$ is divisible by $23$ and
- $d(k) = 23$.
You are given that $S(9) = 263626$ and $S(42) = 6377168878570056$.
Find $S(11^{12})$ and give your answer mod $10^9$.
题意
你要找到一个所有满足一下三个条件的数字数量
假设这个数是$k$
- $k$ $<$ $10^{11^{12}}$
- $k\%23$ = 0
- $k$每个十进制位求和为$23$
分析
这个题目困扰了我两天,我一度以为自己读错题了,主要是数据范围太大了,大的人一点想法都没有$\dots$
下面说正解
虽然数据范围很大,但是我们可以从小数据入手
先看第二个条件$k%23==0$,是否感觉出了一丝丝猫腻?
于是我大胆写了一下,比较好想的就是一定存在一个$n$使得$10^n%23==1$,也就是说存在膜数存在循环,而且显然有循环节是$O(23)$的
于是大胆暴力,找到了,循环节长度为$22$
这也就是说,在十进制下,位数最多有$11^{12}$个,而且这些里面,可以拆分成$22$份,每一份里面,你不管把数字安排到哪里,都是同膜的
于是我们可以简单的把$11^{12}$近似的均分成了$22$份.而且每一份可以单独统计答案
然后问题就转化成了以下两个子问题:
- 找到$a_1,a_2\dots a_{22}$使得$a_1+a_2+\dots +a_{22} = 23$
- 对于每一份就成了一个$a_i$个相同的球放入近似$11^{12}$个盒子里,每个盒子最多放$9$个球,问你方案数
对于第一个子问题,我们显然可以动态规划搞一搞
定义$dp(i,j,k)$表示$a_1+a_2+\dots +a_i == j$并且当前膜数为$k$的方案数
然后暴力转移就行了
关键是第二个子问题不好想,因为盒子数量太大了,必须要有一个$log$的做法
然后就枚举算法(毕竟会的算法不多)
然后就想到了分治,但是能不能分治呢,并不知道,写一发就知道了,然后跑的挺快的(然后就过了)
并不会算分治的玄学复杂度
代码
给大佬递上我奇丑无比的代码 (/ω＼)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
using namespace std;
const int mod = 1e9;
int add(int a,int b){return (a+b)%mod;}
int mul(int a,int b){return 1ll*a*b%mod;}
long long n,m;
void init(){
m = 23;
n = 1;
for(int i = 1;i<=12;i++) n*=11;
}
map<pair<long long,int>,int>mp;
int solve(long long a,int b){///b ball,a boxes
if(a==1) return b<=9;
if(a==0) return b==0;
pair<long long,int> now = make_pair(a,b);
if(mp[now]) return mp[now];
int ret = 0;
long long l = a/2,r = a-l;
for(int i = 0;i<=b;i++) ret = add(ret,mul(solve(l,i),solve(r,b-i)));
return mp[now] = ret;
}
long long dp[30][30][30];
int main(){
init();
dp[0][0][0] = 1;
int w = 1;
for(int i = 0;i<m;i++){
long long has = n/(m-1) + (i<n%22);
for(int j = 0;j<=m;j++){
for(int k = 0;k<m;k++){
for(int t = 0;j+t<=m;t++){
dp[i+1][j+t][(k+w*t)%m] = add(dp[i+1][j+t][(k+w*t)%m],mul(dp[i][j][k],solve(has,t)));
}
}
}
w = w*10%m;
}
cout<<dp[m-1][m][0]<<endl;
return 0;
}
