又是先开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)) 卷积起来的结果,即:
给定 (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。
由于答案是对 (sum_{i=0}^ng_m^k(i)) 求和,所以再乘以一项 (frac{1}{1-x}),那么
然后我就开始想怎么用广义二项式定理推通项公式的事情了。
我想到了对 (n) 进行 (m) 进制拆分,但是推贡献的时候错了一步。用 (1) 去凑 (2m) 的方案数并不等于用 (1) 去凑 (m) 的方案数的平方。
当时我以为有这个关系,然后式子化成了
[ans_1=frac{1}{1-ax^m} left(frac{1}{1-x^m} ight)^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} ight)^k ]然后我发现它挺好解的,于是写了个高斯消元。最终发现推错的那一步时心态爆炸。
Subtask2
(nleq 1000)
这个继整数拆分以后的DP方程也很妙啊。
Subtask4
(k=1)
可以用的数字一共有 (1,m,m^2,m^3dots) 共 (lfloorlog_mn floor) 个。
令 (f[i][j]) 表示用了前 (i) 个数字,当前和为 (j) 的方案数。
令 (j=k* m^(i-1)+r,r< m^(i-1))
注意到后面的都是前面的倍数,所以无论后面的数字如何选择,都不可能改变 (r) 的值,因此可能被用到的 (j) 的 一定是 (k* m^(i-1)+nmod m^(i-1))。
令 (h[i][j]) 表示用了前 (i) 个数字,当前数字和为 (j* m^(i-1)+nmod m^(i-1)) 的方案。
这样 (j) 这一维还是太大。
通过观察和归纳证明,可以得到,对于确定的 (i),(h[i][j]) 是一个关于 (j) 的 (i) 次多项式。
于是我们可以只保留前 (i+1) 项 DP 值,转移使用插值。
一共 (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
",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) 的整数序列,你能够使用的操作只有 ( ext{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(6nlog 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
",sol.size());
for(int i=0;i<(int)sol.size();++i)
printf("%d %d
",sol[i].first,sol[i].second);
return 0;
}