srm 518(有FWT的题QvQ)

发表于   |   分类于   |  

250

Description

从一个字符串中找一字典序最大的字串

Solution

从左至右贪心即可

500

Description

有一个序列，每次可以将一个数$-1$需要花费$1$的代价，问最后使得序列满足$2a[i]\le a[i-1]+a[i+1]$

Solution

因为满足$a[i-1]-a[i]\ge a[i]-a[i+1]$,也就是说序列相邻两项差是递减的，所以每当不满足条件时暴力调整$a[i]$，直到不需要调整为止。想想极限数据调整次数即可直到复杂度是靠谱的。

1000

Description

求符合以下条件的序列个数

  • 1:长度为K
  • 2:每个元素大小不超过L
  • 3:每个数都是质数
  • 4:所有数异或和为0

$K\le{10^{9}},L\le{5\times{10^{4}}}$

Solution

基本的递推方程很容易列出来$f[i][j]$表示前$i$个数异或和为$j$的方案数
$f[i][x\otimes y]=\sum_{0\le x,y\le 2^{16}} f[i-1][x]\times f[1][y]$
$f[1][y]=1$当且仅当$y$为质数且$y\le L$
这样暴力递推显然是$O(KL^2)$的,$i$为偶数时分治一下可以做到$O(L^2\times logK)$的，复杂度还是不行
然后我们可以想到把这个东西搞成类似于FFT的东西。
设向量a,b,c,定义向量之间的运算$　\$,c=a \$ b　$
$c[i\otimes j]=\sum a[i]\times b[j],做变换tf,使得tf(a\$b)=tf(a)\times tf(b),逆变换dft(tf(x))=x$
设$a$向量，$a[i]$表示$i$堆石子异或和为$0\sim 2^{16}$的方案数，$a[1]$在素数位置处为$1$，其他位置为$0$
这样我们只需要用$logK$的时间算出$tf(a[1])^K$,在做逆变换得到$a[k]$即为答案
观察tf和dtf的性质，当只有一个元素时，$tf(x)=dtf(x)=x$
当有两个元素$X=(a,b),Y=(c,d)$时
$Z=X\$Y$
$Z[0]=X[0]\times Y[0]+X[1]\times Y[1]=ac+bd$
$Z[1]=X[0]\times Y[1]+X[1]\times Y[0]=ad+bc$
$另tf(a,b)=(a-b,a+b)$
则$tf(X)\times tf(Y) =(a-b,a+b)\times(c-d,c+d)$
$=((a-b)\times(c-d),(a+b)\times(c+d))$
$=(ac+bd-ad-bc,ac+bd+ad+bc)$
$=tf(ac+bd,ac-bd)$
$=tf((a,b)\$(c,d))$
$=tf(X\$Y)$
$有A，B两向量，用归纳法可证明出tf(A + B) = tf(A) + tf(B) $
$如果我们将X向量分成两段等长的向量X[1],X[2]$
我们归纳一下会发现$tf(X[1],X[2])=(tf(X1) - tf(X2), tf(X1) + tf(X2))$

$(X[1]-X[2])[i]=X[1][i]-X[2][i]$
$(X[1]+X[2])[i]=X[1][i]+X[2][i]$
$将A分为A[1],A[2],B分为B[1],B[2]$
$则依旧可以归纳证出tf( (A1,A2) \$ (B1,B2) ) = tf(A1,A2)\times{tf(B1,B2)}$
$即对任意向量A，B，tf(A\$B)=tf(A)\times{tf(B)}$
$说明当有两个元素时,tf(a,b)=(a-b,a+b)正好就是我们所需要的变换$
然后我们就可以用$tf(X[1],X[2])=(tf(X1) - tf(X2), tf(X1) + tf(X2))$来做啦
算出$tf(a[1])^K$,在做逆变换得到a[K]即为答案

还有不明白的可以看http://apps.topcoder.com/wiki/display/tc/SRM+518

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1<<16,M=1000000007;
ll a[N],inv2;
ll P(ll x,ll y){
	ll tmp=1ll;
	for(;y;y>>=1){
		if(y&1)	tmp=tmp*x%M;
		x=x*x%M;
	}
	return tmp;
}
void trans(int l,int r){
	if(l==r-1)	return ;
	int len=(r-l)/2;
	int mid=l+len;
	trans(l,mid),trans(mid,r);
	for(int i=l;i<mid;++i){
		ll x1=(a[i]-a[i+len]+M)%M,x2=(a[i]+a[i+len])%M;
		a[i]=x1,a[i+len]=x2;
	}
}
void reverse(int l,int r){
	if(r-l==1)	return ;
	int len=(r-l)/2;
	int mid=l+len;
	for(int i=l;i<mid;++i){
		ll x1=a[i],x2=a[i+len];
		a[i]=(x1+x2)*inv2%M;
		a[i+len]=(x2-x1)*inv2%M;
	}
	reverse(l,mid),reverse(mid,r);
}
class Nim{
        public:
        int count(int K, int L){
            inv2=P(2,M-2);
			for(int i=2;i<=L;++i)
				if(!a[i])
					for(int j=i+i;j<=L;j+=i)	a[j]=1;
			for(int i=2;i<=L;++i)	a[i]^=1;
			int Log=1;
			while(Log<=L)	Log<<=1;
			trans(0,Log);
			for(int i=0;i<Log;++i)	a[i]=P(a[i],K);
			reverse(0,Log);
			return a[0];
        }
}

Code