FFT

Prime Distance On Tree 题意 Prime Distance On Tree 给个树，从树上随机选取一对点$u,v$,求$\delta(u,v)$是素数的概率 Solution 可以从生成函数的角度考虑 假设rt是一个树的树根，而且rt的深度是d，将树中节点的深度统计出来，记为$f_{rt，d}$，如果$u,v…$是rt的子节点，那么rt对答案的贡献就是生成函数中素数项的系数，那么问题就是怎么计算生成函数了 $$ \sum_{u,v \in son(rt)} f_{u,1} * f_{v, 1} $$ 这个式子中的素数项系数和与下式是相等的,计算$f$是很简单的 $$ \Big(f_{rt,0}^2 - \sum_{u \in son(rt) }f_{u,1}^2\Big) / 2 $$ 为了确保复杂度不会太高，需要用点分治 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> // #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e5 + 50; #endif const int mod = 1e9 + 7; #include <complex> namespace Prime { vector<int> prime; bool isprime[MAX<<1]; void init(int n){ mset(isprime, 1); isprime[0] = isprime[1] = 0; for(int i = 2; i < n; i++){ if(isprime[i]){ prime.push_back(i); } for(int j = 0; j < prime.size() and prime[j] * i < n; j++){ isprime[i * prime[j]] = 0; if(i * prime[j] == 0) break; } } } } // namespace namePrimPrime namespace FFT { complex<double> a[MAX<<2], b[MAX<<2]; int rev[MAX]; void fft(complex<double> *a, int n, int inv){ int bit = 0; while((1<<bit) < n) bit++; for(int i = 0; i < n; i++){ rev[i] = (rev[i>>1]>>1) | ((i & 1) << (bit-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < n; mid <<= 1){ complex<double> wn(cos(PI/mid), inv*sin(PI/mid)); for(int i = 0; i < n; i += (mid<<1)){ complex<double> w(1, 0); for(int j = 0; j < mid; j++, w *= wn){ complex<double> u = a[i+j], t = w * a[i+j+mid]; a[i+j] = u + t, a[i+j+mid] = u - t; } } } } void product(int n){ fft(a, n, 1); fft(b, n, 1); for(int i = 0; i <= n; i++) a[i] *= b[i]; fft(a, n, -1); } } // namespace nameFFTFFT vector<int> E[MAX]; bool vis[MAX]; // LL dep[MAX]; LL dep[MAX], dep_num[MAX]; int cnt; int siz[MAX]; int dfsG(int u, int p, int& Min, int &rt, int n){ siz[u] = 1; int Max = -1; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i]; if(vis[v] or v == p) continue; siz[u] += dfsG(v, u, Min, rt, n); Max = max(Max, siz[v]); } Max = max(Max, n - siz[u]); if(Max < Min){ Min = Max, rt = u; } return siz[u]; } int dfsN(int u, int p){ int res = 1; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i]; if(vis[v] or v == p) continue; res += dfsN(v, u); } return res; } int find_rt(int u){ int Min = inf; int rt = -1; int n = dfsN(u, -1); dfsG(u, -1, Min, rt, n); return rt; } LL dfs(int u, int p, int d){ // return max_dep dep[cnt++] = d; LL max_dep = d; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i]; if(v == p or vis[v]) continue; max_dep = max(max_dep, dfs(v, u, d+1)); } return max_dep; } LL calcu(int u, int d){ // mset(dep, 0); cnt = 0; dfs(u, -1, d); LL Max = 0; for(int i = 0; i < cnt; i++){ dep_num[dep[i]]++; Max = max(Max, dep[i]); } LL res = 0; int N = 1; while(N <= Max * 2) N <<= 1; for(int i = 0; i < N; i++){ if(i <= Max) FFT::a[i] = FFT::b[i] = complex<double>(dep_num[i], 0); else FFT::a[i] = FFT::b[i] = complex<double>(0, 0); } FFT::product(N); for(int i = 0; i < Prime::prime.size() and Prime::prime[i] <= 2*Max; i++){ res += (LL)(FFT::a[Prime::prime[i]].real() / N + 0.5); } for(int i = 0; i < cnt; i++) dep_num[dep[i]]--; return res; } LL solve(int u){ // vis[u] = 1; int rt = find_rt(u); vis[rt] = 1; LL res = calcu(rt, 0); for(int i = 0; i < E[rt].size(); i++){ if(vis[E[rt][i]]) continue; res -= calcu(E[rt][i], 1); res += solve(E[rt][i]); } // for(int i = 0; i < E[rt].size(); i++){ // if(vis[E[rt][i]]) continue; // res += solve(E[rt][i]); // } return res; } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif int n; scanf("%d", &n); Prime::init(MAX << 1); for(int i = 1; i < n; i++){ int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); } LL up = solve(1); LL down = (LL)n * (n-1); printf("%.7lf\n", 1.0 * up / down); return 0; }

Rock Paper Scissors Lizard Spock 题意： Rock Paper Scissors Lizard Spock 有五种手势，类似于石头剪刀布，有两个串$s, t$,由这五种手势组成，从某个位置开始匹配，如果$t_i$能赢$s_j$得一分，求一个$pos(0\le pos \le len(s)-len(t))$，使得得分最多 Solution： 将上图记为$G$，如果$op_1$可以赢$op_2$，则$G(op_1, op_2)=1$, 枚举可以得分的手势,假设当前手势为$op$, $$ \begin{aligned} t’_i &=(reverse\ t_i == op ? 1 : 0) \newline s’_i &= G[op][s_i] \end{aligned} $$ 将$t’,s’$做卷积，累加每次的结果，再遍历一遍匹配的起始位置，取最大值 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 1e9 + 7; #include <complex> namespace FFT { int rev[MAX * 4]; int cnt[MAX * 4]; void fft(complex<double> *a, int n, int inv){ int bit = 0; while((1<<bit) < n) bit++; for(int i = 0; i < n; i++){ rev[i] = (rev[i>>1]>>1) | ((i & 1) << (bit-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < n; mid <<= 1){ complex<double> wn(cos(PI/mid), inv*sin(PI/mid)); for(int i = 0; i < n; i += (mid<<1)){ complex<double> w(1, 0); for(int j = 0; j < mid; j++, w*=wn){ complex<double> u = a[i+j], t = w * a[i+j+mid]; a[i+j] = u + t, a[i+j+mid] = u-t; } } } } }; int N; char s[MAX], t[MAX], rev_t[MAX]; complex<double> a[MAX*4], b[MAX*4]; int mark[100][100]; void init(){ mark['S']['P'] = 1; mark['P']['R'] = 1; mark['R']['L'] = 1; mark['L']['K'] = 1; mark['K']['S'] = 1; mark['S']['L'] = 1; mark['L']['P'] = 1; mark['P']['K'] = 1; mark['K']['R'] = 1; mark['R']['S'] = 1; } void solve(char op, int n, int m){ for(int i = 0; i < n; i++) a[i] = complex<double>(mark[op][s[i]], 0); for(int i = n; i < N; i++) a[i] = complex<double>(0, 0); for(int i = 0; i < m; i++) b[i] = complex<double>(rev_t[i]==op?1:0, 0); for(int i = m; i < N; i++) b[i] = complex<double>(0, 0); ; FFT::fft(a, N, 1); FFT::fft(b, N, 1); for(int i = 0; i < N;i++) a[i] *= b[i]; FFT::fft(a, N, -1); for(int i = m-1; i <= n-1; i++) FFT::cnt[i] += (int)(a[i].real() / N + 0.5); return; } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif init(); scanf("%s%s", s, t); int n = strlen(s), m = strlen(t); N = 1; while(N <= n+m) N <<= 1; for(int i = 0; i < m; i++) rev_t[i] = t[m-i-1]; vector<char> ops({'R','P', 'S', 'K', 'L'}); for(auto op : ops){ solve(op, n, m); } int ans = 0; for(int i = m-1; i <= n-1; i++){ ans = max(ans, FFT::cnt[i]); // printf("%d ", FFT::cnt[i]); } // puts(""); printf("%d\n", ans); return 0; }

URAL - 1996 题意： URAL - 1996 给两个长度分别为$n, m$的字节串$A,B$，$A$串的最后一位可以修改，代价为$1$，求使得$B$串为$A$串字串的最小代价 Solution : 因为$A$串只有最后最后一位可以修改，所以可以用KMP求出可能匹配的位置，然后计算每个位置的$cost$ 记$A$串最后一位构成的串为$a$， $B$串的为$b$, 假设$pos(0\le pos \le n-m)是可能匹配的位置$，如果将$b$反转得到$b’$, 在此处的的代价为 $$ \sum_{i+j=pos+m-1} [a_i \ne b’_j ] $$ 而 $$ \sum_{i+j=posm-1} a_j * b’_j $$ 可以算出来相等的$1$的个数$cnt_1$，再将$a,b$串取反，再做一次卷积就可以算出$0$相等的个数$cnt_2$，$ans=m-cnt_1-cnt_2$ #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 1e9 + 7; #include <complex> namespace FFT { int rev[MAX]; int cnt[MAX]; void fft(complex<double> *a, int n, int inv){ int bit = 0; while((1 << bit) < n) bit++; for(int i = 0; i < n; i++){ rev[i] = (rev[i>>1]>>1) | ((i & 1) << (bit-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < n; mid <<= 1){ complex<double> wn(cos(PI/mid), inv*sin(PI/mid)); for(int i = 0; i < n; i += (mid<<1)){ complex<double> w(1, 0); for(int j = 0; j < mid; j++, w *= wn){ complex<double> u = a[i+j], t = w * a[i+j+mid]; a[i+j] = u+t, a[i+j+mid] = u-t; } } } } void work(complex<double> *ss, complex<double> *rev_t, int N, int n, int m){ FFT::fft(ss, N, 1); FFT::fft(rev_t, N, 1); for(int i = 0; i <= N; i++) { ss[i] *= rev_t[i]; } FFT::fft(ss, N, -1); for(int i = 0; i <= n-m; i++){ cnt[i] += (int)(ss[i+m-1].real() / N + 0.5); } } }; complex<double> a[MAX],b[MAX]; int x[MAX], y[MAX]; int s[MAX], t[MAX]; complex<double> ss[MAX], rev_t[MAX]; char ch[10]; void input(int *x, int *s, int n){ for(int i = 0; i < n; i++){ scanf("%s", ch); for(int j = 0; j < 6; j++) if(ch[j] == '1') x[i] += 1 << j; s[i] = (ch[7] == '1'); } } struct KMP { int next[MAX]; vector<int> pos; void init(int *x, int n){ next[0] = -1; int k = -1; for(int i = 1; i < n; i++){ while(k > -1 and x[k+1] != x[i]) k = next[k]; if(x[k+1] == x[i]) k++; next[i] = k; } } void work(int *x, int n, int *y, int m){ int k = -1; init(x, n); for(int i =0; i < m; i++){ while(k > -1 and x[k+1] != y[i]) k = next[k]; if(x[k+1] == y[i]) k++; if(k == n-1) { pos.push_back(i-n+1); k = next[k]; } } } }kmp; int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif int n, m; scanf("%d%d", &n, &m); input(x,s,n); input(y, t, m); kmp.init(y, m); kmp.work(y, m, x, n); if(kmp.pos.empty()){ puts("No"); return 0; } int N = 1; while(N <= n+m) N<<=1; for(int i = 0; i < n; i++) ss[i] = complex<double>(s[i], 0); for(int i = 0; i < m; i++) rev_t[i] = complex<double>(t[m-1-i], 0); FFT::work(ss, rev_t, N, n, m); for(int i = 0; i < n; i++) s[i] ^= 1; for(int i = 0; i < m; i++) t[i] ^= 1; for(int i = 0; i < n; i++) ss[i] = complex<double>(s[i], 0); for(int i = n; i < N; i++) ss[i] = complex<double>(0, 0); for(int i = 0; i < m; i++) rev_t[i] = complex<double>(t[m-i-1], 0); for(int i = m; i < N; i++) rev_t[i] = complex<double>(0, 0); FFT::work(ss, rev_t, N, n, m); int res = inf, id = -1; for(int i = 0; i < kmp.pos.size(); i++){ int pos = kmp.pos[i]; // pos += m-1; int cost = m - FFT::cnt[pos]; if(cost < res){ res = cost, id = kmp.pos[i]; } } puts("Yes"); printf("%d %d\n", res, id+1); return 0; }