题解 arc104e Random LIS

Description

arc104e

Solution

观察到 \(n\) 只有 \(6\), 考虑枚举最后 \(x_i\) 之间的大小关系 .
枚举方式是先枚举最后有几个不相等的数 , 然后指定每个 \(x_i\) 的排名 .
最多只有 \(4683\) 种 .

枚举大小关系后可以直接求出最长上升子序列长度 .
然后要算的就是满足这样的排名的 \(x_i\) 的情况数 .

问题可以转化为:
给定 \(lim_{1-n}\)
求满足 \(1\leq x_i\leq lim_i\) 的上升序列 \(x\) 的个数 .
把 \(lim_i\leftarrow lim_i-i+1\)
求满足 \(1\leq x_i\leq lim_i\) 的不降序列 \(x\) 的个数 .
设 \(f_{i,j}\) 为考虑的前 \(i\) 个数 , 最后一个数权值为 \(j\) 的情况数 .
添加 \(lim_{n+1}=\infty\) , 答案为 \(f_{n+1,\infty}\)
\(f\) 的转移式为
\(f_{i,j}=\begin{cases}\sum\limits_{k\leq j}f_{i-1,k},&1\leq j\leq lim_i\\0,&(other)\end{cases}\)
把 \(f_{i}\) 看做一个函数 .
则每次的转移可以看做

1. 修改 \(f_{i}\) 的有效长度 .
2. 把 \(f_{i}\) 变为 \(f_{i}\) 的前缀和 .

观察到 \(f_{i}\) 为最多有 \(i\) 段的分段函数 , 每一段内都可写成不超过 \(i-1\) 次的多项式 .
那么分别对每一段做前缀和 , 然后加上之前的段的贡献即可 .
设之前的段的贡献为 \(bas\) , 该段左端点为 \(l\) .
那么就是给定 \(f(x)=\sum\limits_{i=0}^ma_ix^i\)
计算
\(\begin{aligned}g(x)&=bas+\sum\limits_{i=l}^xf(i)\\&=bas+\sum\limits_{i=l}^x\sum\limits_{j=0}^mi^ja_j\\&=\sum\limits_{i=0}^x\sum\limits_{j=0}^mi^ja_j+bas-\sum\limits_{i=1}^{l-1}\sum\limits_{j=0}^mi^ja_j\end{aligned}\)
记 \(S_i(x)=\sum\limits_{j=1}^xj^i\)
\(\begin{aligned}g(x)&=\sum\limits_{j=0}^ma_jS_j(x)+bas-\sum\limits_{j=0}^ma_jS_j(l-1)\end{aligned}\)
\(S_i(x)\) 可以由公式
\(\displaystyle S_k(x)=\frac{(x+1)^{\underline {k+1}}}{k+1}-\sum\limits_{i=0}^{k-1}\begin{bmatrix}k\\i\end{bmatrix}S_i(x)\)
递推得出 .
证明见
注意这里 \(\begin{bmatrix}k\\i\end{bmatrix}\) 为有符号第一类斯特林数 .
递推公式为 \(\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}-(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}\)
那么这样就可以直接求出 \(f_{n+1}\)
那么最后一段的常数项就是答案 .
时间复杂度 \(O(懒得算)\)

#include
typedef long long ll;
using namespace std;
int read()
{
	int ret=0;bool f=0;char c=getchar();
	while(c>'9'||c<'0')f|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
	return f?-ret:ret;
}
const int mod=1e9+7;
int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=(ll)a*a%mod)if(b&1)ret=(ll)ret*a%mod;return ret;}
int s[10][10];
struct poly
{
	vectorv;
	int&operator[](const int &i){return v[i];}
	void set(int l){v.resize(l);}
	int len(){return v.size();}
	poly operator *(poly x)
	{
		poly ret;
		ret.set(len()+x.len()-1);
		for(int i=0;iv;
	void set(int len)
	{
		while(v.back().l>len)v.pop_back();
		if(v.back().rlen)v.back().r=len;
	}
	void presum()
	{
		int bas=0;
		for(auto &i:v)
		{
			for(int j=0;j&lim)
{
	Data ret;
	for(int i=0;iid[10];int to;
void solve()
{
	static int val[10],f[10];
	for(int i=1;i<=to;i++)if(id[i].empty())return;
	vectortmp;
	for(int i=1;i<=to;i++)
	{
		int mi=1e9;
		for(int &j:id[i])mi=min(mi,a[j]);
		mi=mi-i+1;
		tmp.push_back(mi);
	}
	for(int i=1;i<=to;i++)
		for(int &j:id[i])val[j]=i;
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=0;
		for(int j=1;j