第二题傻子题切掉，第三题暂时看不出来，第四题一看就是数位$dp$dp，分析一会就出来了，然后根据数据范围预知未来我$T$T了，于是就打了一个矩阵乘法，十分优秀。。。

---

T1 棋盘变幻

不会

---

T2 蛋糕店

排序傻子题

---

T3 相似度

全排列傻子题

---

T4 Sam数

若所有位的数字都相差2以内，称这个数为$Sam$Sam数，求位数为$K$K的$Sam$Sam数的个数模$1e9+7$1e9+7

设$f[i][j]$f[i][j]表示为$i$i阶的数，以$j$j为开头的$Sam$Sam 数的方案数，得到方程
$f[i][j]=\sum_{k=max(j-2,0)}^{min(j+2,9)}f[i-1][k]$f[i][j]=∑k=max(j−2,0)min(j+2,9)​f[i−1][k]

因为首位不能为0，所以最终答案就是$\sum_{i=1}^{9}f[n][i]$∑i=19​f[n][i]

然后预测未来之后，我打了矩阵乘法，如图

$dp$dp代码

#include<cstdio>
#include<algorithm>
#define wyc 1000000007
using namespace std;long long f[1000001][10],ans;int n;
signed main()
{
	scanf("%d",&n);
	if(n==1) return printf("10")&0;
	for(register int i=0;i<10;i++) f[1][i]=1;
	for(register int i=2;i<=n;i++)
	 for(register int j=0;j<10;j++)
	  for(register int k=max(j-2,0);k<=min(j+2,9);k++)
		(f[i][j]+=f[i-1][k])%=wyc;
	for(register int i=1;i<10;i++) (ans+=f[n][i])%=wyc;
	printf("%lld",ans);
}

矩阵乘法加速

#include<cstdio>
#include<cstring>
#include<algorithm>
#define XJQ 1000000007
using namespace std;int n;
struct node{long long a[10][10];}ans,x;
long long sum;
inline node mul(node x,node y)
{
	node c;
	memset(&c,0,sizeof(c));
	for(register int k=0;k<10;k++)
	 for(register int i=0;i<10;i++)
	  for(register int j=0;j<10;j++)
	(c.a[i][j]+=x.a[i][k]%XJQ*y.a[k][j]%XJQ)%=XJQ;
	return c;
}
signed main()
{
	scanf("%d",&n);
	if(n==1) return printf("10")&0;
	for(register int i=0;i<10;i++) ans.a[0][i]=1;//初始矩阵
	for(register int i=0;i<10;i++)
	 for(register int j=max(i-2,0);j<=min(i+2,9);j++)
	x.a[j][i]=1;//中间矩阵
	int y=n-1;
	for(;y;x=mul(x,x),y>>=1)
	if(y&1)ans=mul(ans,x);
	for(register int i=1;i<10;i++) (sum+=ans.a[0][i])%=XJQ;
	printf("%lld",sum);
}