题意：
戳这里查看
分析：
我们先不考虑区间的限制设出DP状态,
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示枚举到第
i
i
i个数，单调不降序列最后一位是
j
j
j的方案数
转移方程就是:
if(a
[i
]!=j
) f
[i
][j
]=f
[i
-1][j
]
else f
[i
][j
]=f
[i
-1][k
](k
<=j
)
我们发现可以用矩阵维护，那么对于限定区间的我们考虑通过类似差分的操作
a
n
s
=
I
∗
∏
i
=
1
l
−
1
T
−
1
∗
∏
i
=
1
r
T
ans=I*\prod_{i=1}^{l-1}T^{-1}*\prod_{i=1}^r T
ans=I∗∏i=1l−1T−1∗∏i=1rT
所以我们改为维护逆矩阵和转移矩阵的前缀积，复杂度为
O
(
n
k
2
+
q
k
)
O(nk^2+qk)
O(nk2+qk)
代码：
#include<bits/stdc++.h>
using namespace std
;
namespace zzc
{
const int maxn
= 5e4+5;
const int mod
= 1e9+7;
int f
[maxn
][25],g
[maxn
][25],a
[maxn
],mat
[25][25];
int n
,k
,q
;
int div(int x
)
{
return x
&1?(x
+mod
)>>1:x
>>1;
}
void work()
{
scanf("%d%d",&n
,&k
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&a
[i
]);
for(int i
=1;i
<=k
;i
++)
{
for(int j
=1;j
<=k
;j
++)
{
mat
[i
][j
]=(i
==j
);
}
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=a
[i
];j
++)
{
for(int l
=a
[i
];l
>=j
;l
--)
{
mat
[j
][a
[i
]]=(mat
[j
][a
[i
]]+mat
[j
][l
])%mod
;
}
}
for(int j
=1;j
<=k
;j
++)
{
for(int l
=1;l
<=k
;l
++)
{
f
[i
][j
]=(f
[i
][j
]+mat
[j
][l
])%mod
;
}
}
}
for(int i
=1;i
<=k
;i
++)
{
for(int j
=1;j
<=k
;j
++)
{
mat
[i
][j
]=(i
==j
);
}
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=k
;j
++)
{
g
[i
][j
]=mat
[1][j
];
}
for(int j
=1;j
<=a
[i
];j
++)
{
for(int l
=a
[i
];l
<=k
;l
++)
{
mat
[j
][l
]=(mat
[j
][l
]+mod
-div(mat
[a
[i
]][l
]))%mod
;
}
}
}
scanf("%d",&q
);
for(int i
=1,l
,r
,ans
;i
<=q
;i
++)
{
scanf("%d%d",&l
,&r
);
ans
=0;
for(int j
=1;j
<=k
;j
++)
{
ans
=(ans
+(long long)g
[l
][j
]*f
[r
][j
]%mod
)%mod
;
}
printf("%d\n",ans
);
}
}
}
int main()
{
zzc
::work();
return 0;
}
