题解

看到数据范围，觉得很不对劲——怎么 m m m 最大才2呀？

直觉告诉我这又是一道DP题。于是设 f i , s , t f_{i,s,t} fi,s,t​ 表示当前进行了 i i i 步操作，第一个显示屏的每一个段 亮/暗 程度是 s s s ，第二个是 t t t 的方案数。暴力转移，每 k k k 步把不是数字的状态清空就可以了。这样可以拿到 S u b t a s k 1 , 3 Subtask 1,3 Subtask1,3 的 18 18 18 分。

发现可以把 k k k 步的转移记录下来然后 矩阵乘法 ，时间复杂度 O ( 2 10 m k + 2 15 m log ⁡ 2 n k ) O(2^{10m}k+2^{15m}\log_2 \frac{n}{k}) O(210mk+215mlog2​kn​)，可以拿到 S u b t a s k 2 Subtask 2 Subtask2 的 15 15 15 分。

但是后面的怎么做呢？这种方法似乎没有出路了。

把 k k k 步的转移矩阵 A A A （把两位压在一起）打印出来，可以发现： ∀ x , y , k ∈ [ 0 , 2 5 m ] ∩ Z , A x , x ⨁ k = A y , y ⨁ k \forall x,y,k\in[0,2^{5m}]\cap Z,A_{x,x\bigoplus k}=A_{y,y\bigoplus k} ∀x,y,k∈[0,25m]∩Z,Ax,x⨁k​=Ay,y⨁k​

证明也不难，因为状态 x , y x,y x,y 本质上都是改变了 k k k 位。

那么其实我们只要知道每个改变量的方案就好了。

设 g i , j g_{i,j} gi,j​ 表示操作 i i i 次，改变量是 j j j 的方案数。 O ( 2 10 m log ⁡ 2 k ) O(2^{10m}\log_2 k) O(210mlog2​k) 地 矩阵乘法 就可以了。

然后再设 h i , p , q h_{i,p,q} hi,p,q​ 表示操作 i k ik ik 次，由数字 p p p 变成 q q q 的方案数。

这个东西也可以 矩阵乘法 。

最后再操作完最后 n m o d    k n\mod k nmodk 步即可。

这题有一个比较坑的地方：数据范围中多次出现 k ≤ 1500 k\le 1500 k≤1500 的字样，而实际上是 1 ≤ k ≤ n 1\le k\le n 1≤k≤n ……

---

代码

#include<cstdio>
#include<cstring>
using namespace std;
#define fo(i,l,r) for(register int i=l;i<=r;++i)
typedef long long ll;
#define N 1025
const int num[10]={10,2,9,7,18,21,12,3,29,23},lim[3]={0,9,99},P=1000000007;
int a[N],f[N],ans[N],t1[N],b[105][105],g[105][105],t2[105][105],m;
inline void add(int &x,int y){x+=y;if(x>=P) x-=P;}
inline void pow1(ll y)
{
	for(;y;y>>=1)
	{
		if(y&1)
		{
			fo(i,0,1023) if(a[i])
				fo(j,0,1023) if(f[j])
					add(t1[i^j],1LL*a[i]*f[j]%P);
			fo(i,0,1023) f[i]=t1[i],t1[i]=0;
		}
		fo(i,0,1023) if(a[i])
			fo(j,0,1023) if(a[j])
				add(t1[i^j],1LL*a[i]*a[j]%P);
		fo(i,0,1023) a[i]=t1[i],t1[i]=0;
	}
}
inline void pow2(ll y)
{
	for(;y;y>>=1)
	{
		if(y&1)
		{
			fo(k,0,lim[m]) fo(i,0,lim[m])
				if(g[i][k]) fo(j,0,lim[m])
					if(b[k][j]) add(t2[i][j],1LL*g[i][k]*b[k][j]%P);
			fo(i,0,lim[m]) fo(j,0,lim[m]) g[i][j]=t2[i][j],t2[i][j]=0;
		}
		fo(k,0,lim[m]) fo(i,0,lim[m])
			if(b[i][k]) fo(j,0,lim[m])
				if(b[k][j]) add(t2[i][j],1LL*b[i][k]*b[k][j]%P);
		fo(i,0,lim[m]) fo(j,0,lim[m]) b[i][j]=t2[i][j],t2[i][j]=0;
	}
}
inline int count(int x){return m==1?num[x]<<5:num[x/10]<<5|num[x%10];}
int main()
{
	freopen("display.in","r",stdin);
	freopen("display.out","w",stdout);
	ll k,n;int x;
	scanf("%d%lld%lld%d",&m,&n,&k,&x);
	if(m>1) fo(i,0,9) a[1<<i]=1;
	else fo(i,5,9) a[1<<i]=1;
	f[0]=1,pow1(k);
	fo(i,0,lim[m]) fo(j,0,lim[m])
		b[i][j]=f[count(i)^count(j)];
	g[x][x]=1,pow2(n/k);
	fo(i,0,lim[m]) ans[count(i)]=g[x][i];
	memset(a,0,sizeof a);
	if(m>1) fo(i,0,9) a[1<<i]=1;
	else fo(i,5,9) a[1<<i]=1;
	memset(f,0,sizeof f);
	f[0]=1,pow1(n%k);
	memset(t1,0,sizeof t1);
	fo(i,0,1023) if(ans[i])
		fo(j,0,1023) if(f[j])
			add(t1[i^j],1LL*ans[i]*f[j]%P);
	fo(i,0,lim[m]) printf("%d\n",t1[count(i)]);
	return 0;
}