题目传送门：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
话说这题之前听鏼爷讲过，但又忘了怎么做了
这个记忆力，真是简直了
题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/12/26312367.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2016/12/324324132.pdf
之前鏼爷讲课的时候讲过了
于是这一次直接开始写了
就是每种字母都分开做一遍
符合条件/是该字母就置为1
否则置为0，之后FFT就好
似乎NTT就可以做了？然而不会 QwQ
#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;
}
题目传送门：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
不要问我是怎么知道的
#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;
}