【BZOJ 4259】残缺的字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4259
神犇题解:http://blog.csdn.net/u011542204/article/details/50708834

解题报告

考虑之前的那个DNA的匹配问题
这题似乎也可以做,只是复杂度会乘上一个26
于是考虑优化:
将简单的0/1的多项式变成这个东西: $\sum\limits_{i = 1}^n {{{({a_i} – {b_i})}^2} \cdot {a_i} \cdot {b_i}} $
或者你要展开成这个样子也可以: $\sum {a_i^2[{b_i} \ne 0] – 2\sum {{a_i}{b_i} + \sum {b_i^2[{a_i} \ne 0]} } } $
于是我们发现搞个几次FFT什么的就可以辣!
另外这题在BZOJ上还有双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=4503

话说这题之前听鏼爷讲过,但又忘了怎么做了
这个记忆力,真是简直了

【日常小测】生物进阶

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/12/26312367.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2016/12/324324132.pdf

解题报告

之前鏼爷讲课的时候讲过了
于是这一次直接开始写了

就是每种字母都分开做一遍
符合条件/是该字母就置为1
否则置为0,之后FFT就好
似乎NTT就可以做了?然而不会 QwQ

Code

#include<bits/stdc++.h>
#define E complex<double>
using namespace std;

const int N = 1100000+9;
const double EPS = 1e-3;
const double PI = acos(-1);

int n,m,K,stp,len,a1[N],a2[N],sum[N];
char pat[N]; int vout[N],pos[N];
complex<double> s1[N],s2[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void prework() {
	for (int tmp=1;tmp<=len;tmp<<=1,stp++);
	len = (1<<stp);
	for (int i=1,hig=1<<stp-1;i<=len;i++) {
		pos[i] = pos[i>>1] >> 1;
		if (i & 1) pos[i] |= hig;
	}
}

inline void FFT(complex<double> *arr, int t) {
	for (int i=0;i<len;i++) 
		if (pos[i] < i) swap(arr[pos[i]], arr[i]);
	for (int i=1,num=2;i<=stp;i++,num<<=1) {
		complex<double> wn(cos(2*PI/num),sin(t*2.0*PI/num));
		for (int j=0;j<len;j+=num) {
			complex<double> w(1,0),buf;
			for (int i=j,lim=num/2+j;i<lim;i++,w*=wn) {
				buf = w * arr[i+num/2];
				arr[i+num/2] = arr[i] - buf;
				arr[i] += buf;
			}
		}
	}
	if (!~t) for (int i=0;i<len;i++)
		s1[i].real() /= len;
}

int main() {
	freopen("biology.in","r",stdin);
	freopen("biology.out","w",stdout);
	n = read(); m = read(); 
	K = read(); len = n + m;
	scanf("%s",pat);
	for (int i=0;i<n;i++) {
		if (pat[i] == 'A') a1[i] = 1;
		else if (pat[i] == 'C') a1[i] = 2;
		else if (pat[i] == 'G') a1[i] = 3;
		else if (pat[i] == 'T') a1[i] = 4;
	}
	scanf("%s",pat);
	for (int i=0;i<m;i++) {
		if (pat[i] == 'A') a2[i] = 1;
		else if (pat[i] == 'C') a2[i] = 2;
		else if (pat[i] == 'G') a2[i] = 3;
		else if (pat[i] == 'T') a2[i] = 4;
	}
	
	prework();
	for (int j=1;j<=4;j++) {
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		for (int i=0;i<n;i++) 
			sum[i] = (i>0?sum[i-1]:0) + (a1[i] == j);
		for (int i=0;i<n;i++) 
			s1[i].real() = (sum[min(n-1,i+K)]!=((i-K-1)>=0?sum[i-K-1]:0));
		for (int i=0;i<m;i++) 
			s2[i].real() = (a2[i] == j);
		for (int l=0,r=m-1;l<r;l++,r--) 
			swap(s2[l], s2[r]);
		
		FFT(s1,1); FFT(s2,1);
		for (int i=0;i<len;i++)
			s1[i] = s1[i] * s2[i];
		FFT(s1,-1);
		for (int i=1;i<=n;i++)
			vout[i] += s1[i+m-2].real() + EPS;
	}
	int ret = 0;
	for (int i=1;i<=n;i++)
		ret += (vout[i] == m);
	printf("%d\n",ret);
	return 0;
}

【CodeChef PRIMEDST】Prime Distance On Tree

相关链接

题目传送门:https://www.codechef.com/problems/PRIMEDST
官方题解:https://www.codechef.com/problems/PRIMEDST
神犇题解:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

解题报告

考虑使用点分治来统计答案,实际是求
\(\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}\)
然后发现这货是个卷积的形式,于是点分的时候搞一搞FFT就可以啦!

值得注意的是,在FFT的时候答案可能会爆int
不要问我是怎么知道的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 66000;
const int M = 110000;
const int INF = 1e9;
const double EPS = 1e-2;
const double PI = acos(-1);

int n,head[N],to[M],nxt[M];
LL vout;

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Fast_Fourier_Transform{
	typedef complex<double> E;
	complex<double> a[N<<1];
	int pri[M],vis[M],pos[N<<1],tot,len,stp;
	public:
		Fast_Fourier_Transform() {
			for (int i=2;i<M;i++) {
				if (!vis[i]) pri[++tot] = i;
				for (int j=1;j<=tot&&pri[j]*i<M;j++) {
					vis[i*pri[j]] = 1;
					if (i%pri[j] == 0) break;
				}	
			}
		}
		inline LL solve(int t, int *arr) {
			for (len=1,stp=-1;len<=t*2;len<<=1,++stp);
			memset(a,0,sizeof(E)*(len+9));
			for (int i=0;i<=t;i++) 
				a[i].real() = arr[i];
			for (int i=1;i<len;i++) { 
				pos[i] = pos[i>>1] >> 1;
				if (i & 1) pos[i] |= 1 << stp;
			} 
			
			fft(a, 1);
 			for (int i=0;i<len;i++)
				a[i] *= a[i];
			fft(a, -1);
			LL ret = 0;
			for (int i=1;i<=tot&&pri[i]<=t*2;i++)
				ret += a[pri[i]].real() / len + EPS;
			return ret;
		}
	private:
		inline void fft(E *arr, int t) {
			for (int i=0;i<len;i++)
				if (pos[i] < i) swap(arr[pos[i]], arr[i]);
			for (int k=0,gap=2;k<=stp;k++,gap<<=1) {
				E wn(cos(2*PI/gap),t*sin(2*PI/gap));
				for (int j=0;j<len;j+=gap) {
					complex<double> cur(1, 0),t1,t2;
					for (int i=j;i<j+gap/2;i++,cur*=wn) {
						t1 = arr[i]; t2 = cur * arr[i+gap/2];
						arr[i] = t1 + t2;
						arr[i+gap/2] = t1 - t2;
					}
				}
			}
		}
}FFT;

class Node_Based_Divide_and_Conquer{
	int area_size,cur_ans,root,tot;
	int sum[N],vis[N],cnt[N];
	public:
		inline void solve() {
			area_size = n; cur_ans = INF;
			Get_Root(1, 1);
			work(root, area_size);
		}
	private:
		void work(int w, int sz) {
			vis[w] = 1; 
			vout += solve(w, 0);
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					vout -= solve(to[i], 1);
					area_size = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
					cur_ans = INF; Get_Root(to[i], w);
					work(root, area_size);
				}
			}
		}
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				}
			}
			mx = max(mx, area_size - sum[w]);
			if (mx < cur_ans) {
				cur_ans = mx;
				root = w;
			}	
		}
		LL solve(int w, int bas) {
			memset(cnt,0,sizeof(int)*(tot+9));
			tot = 0; Get_Dis(w, bas, w);
			return FFT.solve(tot, cnt);
		} 
		void Get_Dis(int w, int d, int f) {
			cnt[d]++; 
			tot = max(tot, d);
			for (int i=head[w];i;i=nxt[i]) 
				if (to[i] != f && !vis[to[i]]) 
					Get_Dis(to[i], d+1, w);
		}
}NDC;

int main() {
	n = read();
	for (int i=1;i<n;i++) 
		Add_Edge(read(), read());
	NDC.solve();
	printf("%.10lf\n",(double)vout/n/(n-1));
	return 0;
}