考虑对于$\{a_{i+1},…,a_{n}\}$，在其前面插入$a_{i}$对$x_{i}$的影响（不考虑$a_{1}$到$a_{i-1}$）：

1.$x_{i}=0$，因为其前面没有数字了

2.若$a_{j}+Tx_{j}>a_{i}-T$，则令$x_{j}$加1（字典序最大）

3.若$a_{j}+Tx_{j}\le a_{i}-T$，则$x_{j}$不变

这些操作对于$j$而言是独立的，因此依次遍历$\{a_{j-1},a_{j-2},…,a_{1}\}$即可确定$a_{j}$

对于每一个位置$k$的每一个取值分别dp，设$f[i][j]$表示当遍历到$a_{i}$时$x_{k}=j$的方案数，最终答案即$\sum_{i=1}^{n}i\cdot f[1][i]$，再乘上之后有$k^{n-i}$种序列

时间复杂度为$o(n^{3}k^{2})$（枚举位置$n$，枚举权值$k$，dp状态$n^{2}$，转移$k$），可以通过

1 #include
2 using namespace std;
3 #define N 105
4 #define mod 1000000007
5 int n,m,t,ans,a[N][N],f[N][N];
6 int main(){
7 scanf("%d%d%d",&n,&m,&t);
8 for(int i=1;i<=n;i++) 9 for(int j=1;j<=m;j++)scanf("%d",&a[i][j]); 10 for(int i=1;i<=n;i++){ 11 ans=0; 12 for(int j=1;j<=m;j++){ 13 memset(f,0,sizeof(f)); 14 f[i][0]=1; 15 for(int k=i;k>1;k--)
16 for(int l=0;l<n;l++)
17 for(int x=1;x<=m;x++)
18 if (a[i][j]+t*l<=a[k-1][x]-t)f[k-1][l]=(f[k-1][l]+f[k][l])%mod;
19 else f[k-1][l+1]=(f[k-1][l+1]+f[k][l])%mod;
20 for(int k=1;k<n;k++)ans=(ans+1LL*k*f[1][k])%mod;
21 }
22 for(int j=i+1;j<=n;j++)ans=1LL*ans*m%mod;
23 printf("%d\n",ans);
24 }
25 }