## 【日常小测】生物进阶

### 解题报告

符合条件/是该字母就置为1

### 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];

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);
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

### 解题报告

$$\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}$$

### 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);

LL vout;

inline void Add_Edge(int u, int v) {
static int T = 0;
}

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);
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;
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);
if (to[i] != f && !vis[to[i]])
Get_Dis(to[i], d+1, w);
}
}NDC;

int main() {