又是先开T3的做题顺序，搞我心态。以后我必须先看看题了。

整数拆分

定义 \(f_m(n)\) 表示将 \(n\) 表示为若干 \(m\) 的非负整数次幂的和的方案数。例如，当 \(m = 2\) 的时候，\(f_2(4) = 4\)，一共有 \(\{1, 1, 1, 1\}, \{1, 1, 2\}, \{2, 2\}, \{4\}\) 这 \(4\) 种方案。

定义 \(g^k_m(n)\) 为 \(k\) 个 \(f_m(n)\) 卷积起来的结果，即：

\[g^k_m(n) = \begin{cases}
f_m(n) & k = 1\\
\sum_{i=0}^n(g_m^{k−1}(i) × f_m(n − i)) & \text{otherwise}
\end{cases}
\]

给定 \(n, m, k\)，请求出 \((\sum^n_{i=0} g^k_m(i)) \mod 10^9 + 7\)。

对于所有数据，满足 \(0 ≤ n ≤ 10^{18}, 2 ≤ m ≤ 10^{18}, 1 ≤ k ≤ 20\)。

题解

考场上推生成函数，然而即使推出来了答案的式子我还是不知道怎么做……结果是个DP。

\[f_m=\frac{1}{1-x}\frac{1}{1-x^m}\dots\frac{1}{1-x^{m^{\lfloor\log_mn\rfloor}}}\\
g_m^k=\left(\frac{1}{1-x}\right)^k \left(\frac{1}{1-x^m}\right)^k \dots \left(\frac{1}{1-x^{m^{\lfloor\log_mn\rfloor}}}\right)^k
\]

由于答案是对 \(\sum_{i=0}^ng_m^k(i)\) 求和，所以再乘以一项 \(\frac{1}{1-x}\)，那么

\[ans=\left(\frac{1}{1-x}\right)^{k+1} \left(\frac{1}{1-x^m}\right)^k \dots \left(\frac{1}{1-x^{m^{\lfloor\log_mn\rfloor}}}\right)^k [x^n]
\]

然后我就开始想怎么用广义二项式定理推通项公式的事情了。

我想到了对 \(n\) 进行 \(m\) 进制拆分，但是推贡献的时候错了一步。用 \(1\) 去凑 \(2m\) 的方案数并不等于用 \(1\) 去凑 \(m\) 的方案数的平方。

当时我以为有这个关系，然后式子化成了

\[ans_1=\frac{1}{1-ax^m} \left(\frac{1}{1-x^m}\right)^k [x^{m_1}]
\]

然后我就开始仿造斐波那契数列的通项公式的构造过程，列了个方程

\[\frac{t_0}{1-ax^m} + \frac{t_1}{1-x^m} + \frac{t_2x}{1-x^m} + \dots + \frac{1}{t_kx^{k-1}}=
\frac{1}{1-ax^m} \left(\frac{1}{1-x^m}\right)^k
\]

然后我发现它挺好解的，于是写了个高斯消元。最终发现推错的那一步时心态爆炸。

Subtask2

\(n\leq 1000\)

\[f(n)=\begin{cases}
f(n-1) & n\mod m\neq 0\\
f(n-1)+f(n/m) & n\mod m=0
\end{cases}
\]

这个继整数拆分以后的DP方程也很妙啊。

Subtask4

\(k=1\)

可以用的数字一共有 \(1,m,m^2,m^3\dots\) 共 \(\lfloor\log_mn\rfloor\) 个。

令 \(f[i][j]\) 表示用了前 \(i\) 个数字，当前和为 \(j\) 的方案数。

令 \(j=k* m^(i-1)+r,r< m^(i-1)\)

注意到后面的都是前面的倍数，所以无论后面的数字如何选择，都不可能改变 \(r\) 的值，因此可能被用到的 \(j\) 的一定是 \(k* m^(i-1)+n\mod m^(i-1)\)。

令 \(h[i][j]\) 表示用了前 \(i\) 个数字，当前数字和为 \(j* m^(i-1)+n\mod m^(i-1)\) 的方案。

这样 \(j\) 这一维还是太大。

通过观察和归纳证明，可以得到，对于确定的 \(i\)，\(h[i][j]\) 是一个关于 \(j\) 的 \(i\) 次多项式。

于是我们可以只保留前 \(i+1\) 项 DP 值，转移使用插值。

\[h[i][j]=f[i][j\cdot a_i+n\mod a_i]\\
=\sum_{k=0}^jf[i-1][k\cdot a_i+n\mod a_i]\\
=\sum_{k=0}^jf[i-1][k\frac{a_i}{a_{i-1}}a_{i-1}+\left\lfloor\frac{n \mod a_i}{a_{i-1}}\right\rfloor\cdot a_{i-1}+(n\mod a_i)\mod a_{i-1}]\\
=\sum_{k=0}^jh[i-1][k\frac{a_i}{a_{i-1}}+\left\lfloor\frac{n \mod a_i}{a_{i-1}}\right\rfloor]
\]

一共 \(O(\log n)\) 个因数，每次需要做一次插值，\(O(\log n)\) 次求值，复杂度 \(O(\log^3 n)\)。

CO int N=2000+10;

int fac[N],ifac[N];

struct polynomial{

	int n,y[N];

	int coef[N],pre[N],suf[N];

	void init(){

		for(int i=1;i<=n;++i){

			int sum=mul(ifac[i-1],mul(ifac[n-i],y[i]));

			coef[i]=(n-i)&1?mod-sum:sum;

		}

	}

	int calc(int x){

		if(x<=n-1) return y[x+1];

		pre[0]=1;

		for(int i=1;i<=n;++i) pre[i]=mul(pre[i-1],add(x,mod-(i-1)));

		suf[n+1]=1;

		for(int i=n;i>=1;--i) suf[i]=mul(suf[i+1],add(x,mod-(i-1)));

		int ans=0;

		for(int i=1;i<=n;++i) ans=add(ans,mul(coef[i],mul(pre[i-1],suf[i+1])));

		return ans;

	}

}h[N];

LL pw[N];int lg;

LL a[N];int cnt;

int main(){

	freopen("split.in","r",stdin),freopen("split.out","w",stdout);

	LL n=read<LL>(),m=read<LL>();

	int K=read<int>();

	lg=0,pw[0]=1;

	for(;pw[lg]<=n/m;++lg) pw[lg+1]=pw[lg]*m;

	cnt=0,a[0]=1;

	for(int i=0;i<=lg;++i)

		for(int j=1;j<=K;++j) a[++cnt]=pw[i];

	fac[0]=1;

	for(int i=1;i<=cnt;++i) fac[i]=mul(fac[i-1],i);

	ifac[cnt]=fpow(fac[cnt],mod-2);

	for(int i=cnt-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);

	h[0].n=1,h[0].y[1]=1;

	h[0].init();

	for(int i=1;i<=cnt;++i){

		h[i].n=i+1;

		LL r=n%a[i]/a[i-1];

		for(int j=0;j<=i;++j){

			h[i].y[j+1]=h[i-1].calc((a[i]/a[i-1]*j+r)%mod);

			h[i].y[j+1]=add(h[i].y[j],h[i].y[j+1]);

		}

		h[i].init();

	}

	printf("%d\n",h[cnt].calc((n/a[cnt])%mod));

	return 0;

}

我觉得如果我能猜到那个生成函数的系数是多项式的话，我还是做得出来的。但毕竟见识太少，我只会中规中矩的方法，不会直接想到拉格朗日插值和BM算法。

多项式证明

首先 \(\frac{1}{1-x}\) 的系数是多项式。

通过打表找规律，两个系数是多项式的生成函数卷积后的生成函数的系数也是多项式。\(n\) 次的多项式乘以 \(m\) 次的多项式得到的是 \(n+m+1\) 次的多项式。

那么 \((\frac{1}{1-x})^{k+1}\) 就是一个 \(k\) 次多项式。往 \(\frac{1}{1-x^m}\) 合并的时候，我们只会用 \(x\) 的次数是 \(m\) 的自然数倍的项，分离常数后它还是一个 \(k\) 次多项式；但是 \(\frac{1}{1-x^m}\) 分离常数后变成了 \(0\) 次多项式，所以 \((\frac{1}{1-x})^{k+1} (\frac{1}{1-x^m})^k\) 就是一个 \(2k\) 次多项式。

如此归纳下去，就可证明那个 DP 状态一直是多项式了。

简单计数

给定一个长度为 \(n\) 的序列 \(s\)。共询问 \(m\) 次，每次询问给定一个数字 \(k\) 和一个固定长度 \(l\)，以及 \(k\) 个整数 \(x_1, x_2, \dots, x_k\)。请求出，如果将区间 \([x_1, x_1 + l − 1]，[x_2, x_2 + l − 1],\dots,[x_k, x_k + l − 1]\) 按照顺序前后拼接在一起得到的序列中，有多少回文子串，序列从 \(1\) 开始编号。回文子串的定义是，这个序列从前往后和从后往前是一样的。

对于所有数据，满足 \(n ≤ 10^5 , m ≤ 10^5 , ∑k ≤ 10^5 , ∑k × l ≤ 10^9 , x_i + l − 1 ≤ n, 1 ≤ s_i ≤ n\)。

题解

咕咕咕。

排序

给出一个长度为 \(n\) 的整数序列，你能够使用的操作只有 \(\text{rev}(l, r)\)，表示将闭区间 \([l, r]\) 内的数字翻转，需要的代价是 \(r − l + 1\), 你需要在 \(4 × 10^6\) 的代价内最大化最终序列的 LIS 长度，LIS 表示最长上升子序列。

只有你使用的操作的代价不超过限制，并且最终得到的序列的 LIS 和理论上能够得到的最大值一样的时候，才可以得分。

对于所有数据，满足 \(n ≤ 32000, 0 ≤ 序列中的数字 ≤ 32000\)。

题解

题目让你最大化LIS，然而其实完全可以排好序……所以说我们要有大胆猜结论的能力。并且这道题是考场上AC人数最多的。

Subtask3

考虑 01 序列如何排序。其实归并排序就可以，每次我们把左区间所有的 1 和右区间所有的 0 ，交换一下。

0101

0011

值域 \([0,5]\) 同理，我们可以每次把一种数字分出来。

012345012345

012344321055

001234432155

001123443255

001122344355

001122334455

复杂度 \(O(6n\log n)\)。

Subtask4

值域较大，对所有数字再进行一次分治即可。

具体而言，就是按位从高到低做。有点像倒着的基数排序。

CO int N=32000+10;

int a[N];

vector<pair<int,int> > sol;

void reverse(int l,int r){

	reverse(a+l,a+r+1);

	sol.push_back(make_pair(l,r));

}

void sol01(int l,int r,int w){

	if(l==r) return;

	int mid=(l+r)>>1;

	sol01(l,mid,w),sol01(mid+1,r,w);

	int ql=0;

	for(int i=mid;i>=l;--i)

		if(a[i]>>w&1) ql=i;

	int qr=0;

	for(int i=mid+1;i<=r;++i)

		if(~a[i]>>w&1) qr=i;

	if(ql and qr) reverse(ql,qr);

}

void solve(int l,int r,int w){

	if(l>r or w==-1) return;

	sol01(l,r,w);

	int mid=0;

	for(int i=l;i<=r;++i)

		if(~a[i]>>w&1) mid=i;

	if(!mid) solve(l,r,w-1);

	else solve(l,mid,w-1),solve(mid+1,r,w-1);

}

int main(){

	freopen("rev.in","r",stdin),freopen("rev.out","w",stdout);

	int n=read<int>();

	for(int i=1;i<=n;++i) read(a[i]);

	solve(1,n,14);

	printf("%zd\n",sol.size());

	for(int i=0;i<(int)sol.size();++i)

		printf("%d %d\n",sol[i].first,sol[i].second);

	return 0;

}

巴特西

test20191205 WC模拟赛

整数拆分

题解

Subtask2

Subtask4

多项式证明

简单计数

题解

排序

题解

Subtask3

Subtask4

最新文章

热门文章