Good Numbers[hdu6618]

发表于 分类于

Good Numbers

题意

定义一个正整数 $n$ 是好数当且仅当 $n$ 在8进制表示下所有的数码出现的次数为**3的倍数(出现0次亦可)**。

有多少个 $k$ 位的8进制数（不含前导0），满足这个数是好的，且是 $p$ 的倍数。对 $10^9+9$ 取模。

例如：当 $k=3,p=2$ 时，好数有 $222(8),444(8),666(8)$ 三个。

$1\le k \le 10^{18},p<8$

题解

因为只有8进制，考虑状压dp，设 $f[i][S][j]$ 表示考虑第 $i$ 位，8个位出现次数模 $3$ 的状态，当前数模 $p$ 的余数为 $j$ 的方案数。时间复杂度 $O(8kpw)$，其中 $w$ 为 $3^8=6561$。

发现瓶颈在于 $k$。

考虑优化 $k$，可以倍增dp，类似于快速幂的处理方法。

考虑从第 $i$ 位转移到第 $2i$ 位：

把 $2i$ 个位拆成前 $i$ 位和后 $i$ 位，枚举这两个状态。

那么有：

$$f[2i][S_1\bigoplus S_2][j_1+t\times j_2]+=f[i][S_1][j_1]\times f[i][S_2][j_2]$$

其中 $\bigoplus$ 代表3进制不进位加法（异或）。

从 $i$ 位转移到 $i+1$ 位比较容易。

时间复杂度 $O(w^2p^2\log k)$。

这时又多了一个瓶颈 $w^2$。

枚举了 $j_1$ 和 $j_2$ 后发现 $S_1,S_2$ 很像异或卷积形式。

实际上就是 3进制的异或卷积，用 3进制FWT加速。

在模 $10^9+9$ 意义下 $1$ 的三次单位根存在。

优化到 $O(wp^2\log w\log k)$

注意前导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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define ll long long
#define M 6561
#define mem(x) memset((x),0,sizeof(x))
const ll mod=1e9+9;
const ll G=2;
inline ll Pow(ll x,int y)
{
	ll ans=1;
	for(;y;y>>=1,x=x*x%mod) if(y&1) ans=ans*x%mod;
	return ans;
}
const ll w1=Pow(G,(mod-1)/3);
const ll w2=Pow(G,(mod-1)/3*2);
const ll inv3=Pow(3,mod-2);
const ll inv2=Pow(2,mod-2);
inline void fwt(ll *a,int n,int opt)
{
	static ll c[3],b[3];
	for(int i=1,len=3;len<=n;i*=3,len*=3)
		for(int j=0;j<n;j+=len)
			for(int k=0;k<i;k++)
			{
				for(int l=0;l<3;l++) b[l]=a[j+k+l*i];
				if(opt==1)
				{
					c[0]=(b[0]+b[1]+b[2])%mod;
					c[1]=(b[0]+b[1]*w1+b[2]*w2)%mod;
					c[2]=(b[0]+b[1]*w2+b[2]*w1)%mod;
					for(int l=0;l<3;l++) b[l]=c[l];
				}
				else
				{
					c[0]=(b[0]+b[1]+b[2])%mod;
					c[1]=(b[0]+b[1]*w2+b[2]*w1)%mod;
					c[2]=(b[0]+b[1]*w1+b[2]*w2)%mod;
					for(int l=0;l<3;l++) b[l]=c[l]*inv3%mod;
				}
				for(int l=0;l<3;l++) a[j+k+l*i]=b[l];
			}
}
ll p3[10],a[8][M],_a[8][M],b[8][M],_b[8][M],c[8][M],n;
int p;
int main()
{
	p3[0]=1;
	for(int i=1;i<8;i++) p3[i]=p3[i-1]*3;
	while(~scanf("%lld%d",&n,&p))
	{
		ll now,tmp;
		for(int t=59;~t;t--)
		if((now=(n>>t)))
			if(now==1)
			{
				for(int i=0;i<p;i++) mem(a[i]),mem(b[i]);
				for(int i=1;i<8;i++) a[i%p][p3[i]]=b[i%p][p3[i]]=1;
				a[0][1]=1;//之后就可以有前导0
				for(int i=0;i<p;i++) fwt(a[i],M,1),fwt(b[i],M,1),memcpy(c[i],a[i],sizeof(a[i]));
				tmp=8%p;
			}
			else
			{
				for(int i=0;i<p;i++) mem(_a[i]),mem(_b[i]);
				for(int i=0;i<p;i++)
					for(int j=0;j<p;j++)
					{
						int l=(i*tmp+j)%p;
						for(int k=0;k<M;k++)
							(_a[l][k]+=a[i][k]*a[j][k])%=mod,
							(_b[l][k]+=b[i][k]*a[j][k])%=mod;
					}
				for(int i=0;i<p;i++) memcpy(a[i],_a[i],sizeof(_a[i])),memcpy(b[i],_b[i],sizeof(_b[i]));
				tmp=tmp*tmp%p;
				if(!(now&1ll)) continue;
				for(int i=0;i<p;i++) mem(_a[i]),mem(_b[i]);
				for(int i=0;i<p;i++)
					for(int j=0;j<p;j++)
					{
						int l=(i*8+j)%p;
						for(int k=0;k<M;k++)
							(_a[l][k]+=a[i][k]*c[j][k])%=mod,
							(_b[l][k]+=b[i][k]*c[j][k])%=mod;
					}
				for(int i=0;i<p;i++) memcpy(a[i],_a[i],sizeof(a[i])),memcpy(b[i],_b[i],sizeof(b[i]));
				tmp=tmp*8%p;
			}
		fwt(b[0],M,-1);
		printf("%lld\n",b[0][0]);
	}
	return 0;
}