我要死了

题目描述

给定长度为 (n) 的排列，求出在 (k) 次冒泡排序的交换之后的结果。

(nle 10^6)。

解法

草原题还是不会... 令处在位置 (i) 的数字之前大于它的数字个数为 (d_i)，那么 (k) 轮冒泡排序之后这个数字被交换的次数就是 (min{d_i,k})！

所以可以二分冒泡排序的轮数 (x)，对于 (d_ige k)，这个数字就会挪到 (i-k) 这个位置。其余的数字一定是从小到大排列的，这样才能保证逆序对为零。最后的次数再暴力冒泡即可。

( ext{Bloody Regina})

题目描述

给定长度为 (n) 的数列 ({a})，每个数字在 ([1,m]) 之间，定义满足条件的三元组 ((x,y,z)) 为：

(x=y=z)；
(y=x+1,z=y+1)。

每个元素只能属于一个三元组。请求出你能选出的最大三元组数量。

(n,mle 10^6)。

解法

首先按值域来考虑。不妨思考 (dp_{i,j,k}) 为第 (i) 位，中间为 (i) 的三元组（此处及下文指的都是第二种情况）个数为 (j)，第一个为 (i) 的三元组个数为 (k) 的答案。

为什么定义这样的状态？考虑从 (i-1) 转移的过程，显然以 (i-1) 为结尾的三元组个数已经和 (i) 没有关系了（更准确地说，这个关系体现在 (mathtt{dp}) 值中）。

这个状态是过不了的，但我们发现，当同样的三元组个数为 (3) 时，就可以拆成 (3) 个第一种情况的三元组。所以 (j,k) 可以限制在 (2) 以内！

转移时再枚举以 (i) 为开始地三元组个数 (l)：

[dp_{i,k,l}=max{dp_{i-1,j,k}+l+(a_i-j-k-l)/3} ]

( ext{Morpho})

题目描述

给定长度为 (n) 的序列，有 (m) 个操作：

将区间 ([l,r]) 中的数字加上 (k)。
将区间 ([l,r]) 中的数字变为相反数。
询问从 ([l,r]) 中选择 (k) 个数字相乘的所有方案的和，取模 (10^8+7)（出题人想要卡这个质数燃鹅一个生物也没进坑）。

(n,mle 5cdot 10^4,1le kle min{20,r-l+1})。

解法

首先有一个 (mathcal O(nmk)) 的 (mathtt{dp})，不做展开。当时就在想矩乘，然而这是区间修改（应该也是可以推的），而且矩乘复杂度显然不对... 思维就陷入了僵局。

事实上，如果将每一项看作 ((a_ix+1))，将区间中每一项乘起来，答案就是这个多项式第 (k) 项的系数！

这样单次合并就变成 (mathcal O(k^2)) 的啦！接下来考虑如何修改：

取反。这个比较简单，就是多项式奇数项取反即可。
加 (k)。令多项式长度为 (t)，这实际上就变成了 (prod_{i=1}^t(a_i+k))。当选择 (p) 项 (a) 时，对应系数就是 (k^{t-p})。实际上就有：
[f(i)=sum_{j=0}^i inom{t-(i-j)}{j}cdot k^{j}cdot f'(i-j) ]
这个是 (mathcal O(k^2)) 的。

总复杂度 (mathcal O(k^2 nlog n))。有个需要注意的点是，虽然我们只需要 (le 20) 的项，但是存储长度需要准确，这是为了 "加 (k)" 操作的正确性。

代码

#include <cstdio>
#define print(x,y) write(x),putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while((s=getchar())>'9' or s<'0')
        f |= (s=='-');
    while(s>='0' and s<='9')
        x = (x<<1)+(x<<3)+(s^48),
        s = getchar();
    return f?-x:x;
}

template <class T>
inline void write(const T x) {
    if(x<0) {
        putchar('-');
        write(-x);
        return;
    }
    if(x>9) write(x/10);
    putchar((x-x/10*10)^48);
}

#include <cctype>
#include <cstring>

const int mod = 1e8+7;
const int maxn = 5e4+5;

int n,m,C[maxn][22];
struct node {
	int f[21],la,len; bool rev;
	inline int& operator [] (int i) {return f[i];}
	
	void Print() {
		for(int i=0;i<=len;++i)
			print(f[i],' '); puts("");
	}
} t[maxn<<2];

inline int inc(int x,int y) {
	return x+y>=mod?x+y-mod:x+y;
}

inline int Min(int x,int y) {
	return x<y?x:y;
}

void pushUp(node &t,node &a,node &b) {
	t.len = a.len+b.len; memset(t.f,0,sizeof t.f);
	for(int i=Min(20,t.len);~i;--i) 
		for(int j=0; j<=a.len and j<=i; ++j)
			t[i] = inc(t[i],1ll*a[j]*b[i-j]%mod);
}

void build(int o,int l,int r) {
	if(l==r) {
		t[o][1]=(read(9)%mod+mod)%mod;
		t[o].len=t[o][0]=1; return;
	}
	int mid=l+r>>1;
	build(o<<1,l,mid),build(o<<1|1,mid+1,r);
	pushUp(t[o],t[o<<1],t[o<<1|1]);
}

void Rev(node &t) {
	t.rev^=1,t.la=(mod-t.la)%mod;
	for(int i=1,siz=Min(t.len,20);i<=siz;i+=2)
		t[i] = (mod-t[i])%mod;
}

void Add(node &t,int k) {
	t.la = inc(t.la,k);
	for(int i=Min(20,t.len);~i;--i) {
		int pw=k;
		for(int j=1;j<=i;++j)
			t[i] = inc(t[i],1ll*t[i-j]*pw%mod*C[t.len-i+j][j]%mod),
			pw = 1ll*pw*k%mod;
	}
}

void pushDown(int o) {
	if(t[o].rev) {
		Rev(t[o<<1]),Rev(t[o<<1|1]);
		t[o].rev=0;
	}
	if(t[o].la) {
		Add(t[o<<1],t[o].la),
		Add(t[o<<1|1],t[o].la);
		t[o].la=0;
	}
}

void ModifyRev(int o,int l,int r,int L,int R) {
	if(l>=L and r<=R) return Rev(t[o]);
	int mid=l+r>>1; pushDown(o);
	if(L<=mid) ModifyRev(o<<1,l,mid,L,R);
	if(R>mid) ModifyRev(o<<1|1,mid+1,r,L,R);
	pushUp(t[o],t[o<<1],t[o<<1|1]);
}

void ModifyAdd(int o,int l,int r,int L,int R,int k) {
	if(l>=L and r<=R) return Add(t[o],k);
	int mid=l+r>>1; pushDown(o);
	if(L<=mid) ModifyAdd(o<<1,l,mid,L,R,k);
	if(R>mid) ModifyAdd(o<<1|1,mid+1,r,L,R,k);
	pushUp(t[o],t[o<<1],t[o<<1|1]);
}

node Query(int o,int l,int r,int L,int R) {
	if(l>=L and r<=R) return t[o];
	int mid=l+r>>1; pushDown(o);
	if(R<=mid) return Query(o<<1,l,mid,L,R);
	if(L>mid) return Query(o<<1|1,mid+1,r,L,R);
	node lhs = Query(o<<1,l,mid,L,R);
	node rhs = Query(o<<1|1,mid+1,r,L,R);
	node ret;
	return pushUp(ret,lhs,rhs),ret;
}

void init() {
	C[0][0]=1;
	for(int i=1;i<=maxn-5;++i) {
		C[i][0]=1;
		for(int j=1;j<=Min(20,i);++j)
			C[i][j] = inc(C[i-1][j],C[i-1][j-1]);
	}
}

int main() {
    n=read(9),m=read(9),read(9); init();
	build(1,1,n); char ch; int l,r,k,ans=0;
	while(m--) {
		while(!isalpha(ch=getchar()));
		l = (read(9)^ans), r = (read(9)^ans);
		if(ch^'R') k = ((read(9)^ans)%mod+mod)%mod;
		if(ch=='R') ModifyRev(1,1,n,l,r);
		else if(ch=='I') ModifyAdd(1,1,n,l,r,k);
		else print(ans=Query(1,1,n,l,r)[k],'
');
	}
    return 0;
}