## 题目描述

Given a sequence $a$ and an empty sequence $b$, each element in $a$ is added to $b$ with probability $P$ (independently to the other elements). Denote $s=\bigoplus_{i=1}^{|b|} b_i$, where $\oplus$ denotes bitwise xor and $s=0$ if $b$ is empty. Find the expected value of $s^2$.

## 算法分析

\begin{align} \sum_s s^2P(s) &= \sum_s (\sum_{i=0}^{29} [s二进制第i位为1] 2^i)^2P(s) \\ &= \sum_s P(s) \sum_{i=0}^{29} [s二进制第i位为1] 2^i \sum_{j=0}^{29} [s二进制第j位为1] 2^j \\ &= \sum_s P(s) \sum_{i=0}^{29} \sum_{j=0}^{29} [s二进制第i位和第j位都为1] 2^{i+j} \\ &= \sum_{i=0}^{29} \sum_{j=0}^{29} P(s二进制第i位和第j位都为1) 2^{i+j} \end{align}

## 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 100005, MOD = 1000000007;

int a[N], f[N][2][2];

int power(int a, int b) {
int ret = 1;
for (; b; b >>= 1) {
if (b & 1) {
ret = 1ll * ret * a % MOD;
}
a = 1ll * a * a % MOD;
}
return ret;
}

int main() {
int n, x, y;
scanf("%d%d%d", &n, &x, &y);
int p = 1ll * x * power(y, MOD - 2) % MOD, q = (MOD + 1 - p) % MOD;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
int ans = 0, ans2 = 0;
f[0][0][0] = 1;
for (int i = 0; i < 30; ++i) {
for (int j = i; j < 30; ++j) {
for (int k = 1; k <= n; ++k) {
for (int _i = 0; _i < 2; ++_i) {
for (int _j = 0; _j < 2; ++_j) {
int __i = _i ^ (a[k] >> i & 1);
int __j = _j ^ (a[k] >> j & 1);
f[k][_i][_j] = (1ll * f[k - 1][_i][_j] * q + 1ll * f[k - 1][__i][__j] * p) % MOD;
}
}
}
ans = (ans + (1ll << i + j + (i != j)) % MOD * f[n][1][1]) % MOD;
}
}
printf("%d\n", ans);
return 0;
}

## 题目描述

You have an unbalanced coin, the state of which (head or tail) after tossing depends on the previous state. If the head side is up now, the probability that the coin is still head up after tossing is $p$, and the probability that the tail side comes up is $1-p$. Similarly, if the tail side is up now, the probability that the coin is still tail up after tossing is $p$, and the probability that the head side comes up is $1-p$.

Assume the coin is head up initially. You will then toss it for $n$ times, during these $n$ times, every time the head side is up, you will get one score. What is the probability that you will get exactly $k$ score for $k=0,1,2,\cdots,n$?

## 算法分析

\begin{align} f_{i,0,j} &= f_{i-1,0,j-1} \times p+f_{i-1,1,j-1} \times (1-p) \\ f_{i,1,j} &= f_{i-1,0,j} \times (1-p)+f_{i-1,1,j} \times p \end{align}

\begin{align} F_{i,0} &= F_{i-1,0} \times px+F_{i-1,1} \times (1-p)x \\ F_{i,1} &= F_{i-1,0} \times (1-p)+F_{i-1,1} \times p \end{align}

$$$$\left[\begin{matrix} px & (1-p)x \\ 1-p & p\end{matrix}\right] \left[\begin{matrix} F_{i-1,0} \\ F_{i-1,1} \end{matrix}\right]= \left[\begin{matrix} F_{i,0} \\ F_{i,1} \end{matrix}\right]$$$$

## 代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 200005;
double const PI = acos(-1);

int rev[N];

struct Complex {
double a, b;
Complex(double _a = 0, double _b = 0) : a(_a), b(_b) {}
friend Complex operator+(Complex const &x, Complex const &y) {
return Complex(x.a + y.a, x.b + y.b);
}
friend Complex operator-(Complex const &x, Complex const &y) {
return Complex(x.a - y.a, x.b - y.b);
}
friend Complex operator*(Complex const &x, Complex const &y) {
return Complex(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a);
}
friend Complex operator/(Complex const &x, double const &y) {
return Complex(x.a / y, x.b / y);
}
} wn[N], A[2][2][N], B[2][2][N], C[2][2][N];

int init(int n) {
int len = 1, p = 0;
for (; len < n; len <<= 1, ++p) ;
for (int i = 1; i < len; ++i) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << p - 1;
}
for (int i = 0; i < len >> 1; ++i) {
wn[i] = Complex(cos(2 * PI / len * i), sin(2 * PI / len * i));
}
return len;
}

void fft(Complex *a, int len, bool inv = 0) {
for (int i = 0; i < len; ++i) {
if (i < rev[i]) {
std::swap(a[i], a[rev[i]]);
}
}
for (int i = 1; i < len; i <<= 1) {
for (int j = 0; j < len; j += i << 1) {
for (int k = 0; k < i; ++k) {
Complex x = a[j + k], y = wn[len / (i << 1) * k] * a[j + i + k];
a[j + k] = x + y;
a[j + i + k] = x - y;
}
}
}
if (inv) {
std::reverse(a + 1, a + len);
for (int i = 0; i < len; ++i) {
a[i] = a[i] / len;
}
}
}

struct Matrix {
int n[2][2];
double *a[2][2];

friend Matrix operator*(Matrix const &x, Matrix const &y) {
int len = init(x.n[0][0] + y.n[0][0] - 1);
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < len; ++k) {
A[i][j][k] = k < x.n[i][j] ? x.a[i][j][k] : 0;
B[i][j][k] = k < y.n[i][j] ? y.a[i][j][k] : 0;
C[i][j][k] = 0;
}
fft(A[i][j], len);
fft(B[i][j], len);
}
}
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < len; ++l) {
C[i][j][l] = C[i][j][l] + A[i][k][l] * B[k][j][l];
}
}
fft(C[i][j], len, 1);
}
}
Matrix ret;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret.n[i][j] = 0;
for (int k = 0; k < 2; ++k) {
ret.n[i][j] = std::max(ret.n[i][j], x.n[i][k] + y.n[k][j] - 1);
}
ret.a[i][j] = new double[ret.n[i][j]];
for (int k = 0; k < ret.n[i][j]; ++k) {
ret.a[i][j][k] = C[i][j][k].a;
}
}
}
return ret;
}
} base, ans;

int main() {
int n;
double p;
scanf("%d%lf", &n, &p);
base.n[0][0] = base.n[0][1] = 2;
base.n[1][0] = base.n[1][1] = 1;
base.a[0][0] = new double[2];
base.a[0][0][0] = 0;
base.a[0][0][1] = p;
base.a[0][1] = new double[2];
base.a[0][1][0] = 0;
base.a[0][1][1] = 1 - p;
base.a[1][0] = new double;
base.a[1][0][0] = 1 - p;
base.a[1][1] = new double;
base.a[1][1][0] = p;
ans.n[0][0] = ans.n[1][1] = 1;
ans.a[0][0] = new double;
ans.a[0][0][0] = 1;
ans.a[1][1] = new double;
ans.a[1][1][0] = 1;
int b = n;
for (; b;) {
if (b & 1) {
ans = ans * base;
}
if (b >>= 1) {
base = base * base;
}
}
for (int i = 0; i <= n; ++i) {
printf("%.10f\n", ans.a[0][0][i] + ans.a[1][0][i]);
}
return 0;
}

## 题目描述

You are a master of barbeque, and now you are trying to string dumplings with a bamboo stick.

The dumplings are placed in a $n \times m$ grid. Each grid contains exactly one dumpling. The color of each dumpling is red ("R"), green ("G") or white ("W").

You can choose three consecutive grids from left to right, or from top to bottom, and string the corresponding dumplings into a string from left to right or from top to bottom. So there will be exactly three dumplings on a string, let’s denote a string of dumpling by their colors in order.

Now, you want to make strings "RGW" as many as possible. Note that the dumplings can not be reused in multiple strings. So how many strings "RGW" can you make?

## 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 3005;
char mp[N][N];
int f[N][N][3];

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", mp[i] + 1);
}
for (int k = 2; k <= n + m; ++k) {
for (int i = 1; i < k; ++i) {
int j = k - i;
if (i <= n && j <= m) {
f[i][j][0] = std::max(f[i - 1][j + 1][0], std::max(f[i - 1][j + 1][1], f[i - 1][j + 1][2]));
if (mp[i][j - 1] == 'R' && mp[i][j] == 'G' && mp[i][j + 1] == 'W') {
f[i][j][1] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][1]) + 1;
}
if (mp[i - 1][j] == 'R' && mp[i][j] == 'G' && mp[i + 1][j] == 'W') {
f[i][j][2] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][2]) + 1;
}
}
}
}
int ans = 0;
for (int i = 1; i < n; ++i) {
ans += std::max(f[i][1][0], std::max(f[i][1][1], f[i][1][2]));
}
for (int i = 1; i <= m; ++i) {
ans += std::max(f[n][i][0], std::max(f[n][i][1], f[n][i][2]));
}
printf("%d\n", ans);
return 0;
}

## 代码

/*
* Your nature demands love and your happiness depends on it.
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
std::pair<double, double> pair() {
return std::make_pair(x, y);
}
friend Point operator+(Point const &a, Point const &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(Point const &a, Point const &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(Point const &a, Point const &b) {
return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
Point operator/(double const &n) {
return Point(x / n, y / n);
}
} wn[T], A[T], B[T];

int init(int n) {
int m = n, l = 0;
for (n = 1; n <= m; n <<= 1, ++l)
;
for (int i = 1; i < n; ++i)
rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
for (int i = 0; i < n >> 1; ++i)
wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
return n;
}

void fft(Point *a, int n, int inv = 0) {
for (int i = 0; i < n; ++i)
if (i < rev[i])
std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += i << 1)
for (int k = 0; k < i; ++k) {
Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
a[j + k] = x + y, a[j + k + i] = x - y;
}
if (inv) {
std::reverse(a + 1, a + n);
for (int i = 0; i < n; ++i)
a[i] = a[i] / n;
}
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
int a, b, c;
} li[M];

void update(int l, int r) {
int mid = l + r >> 1, len = init(r - l + r - mid - 2);
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < len; ++j)
A[j] = B[j] = 0;
for (int j = mid + 1; j <= r; ++j)
A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
for (int j = 1; j <= r - l; ++j)
B[j - 1] = p[i][j];
fft(A, len), fft(B, len);
for (int j = 0; j < len; ++j)
A[j] = A[j] * B[j];
fft(A, len, 1);
for (int j = l; j <= mid; ++j)
s[i][j] += A[r - j - 1].x;
}
}

void solve(int l, int r) {
if (l == r) {
for (int i = 1; i <= m; ++i)
f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
return;
}
int mid = l + r >> 1;
solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
scanf("%d%d%d%d", &n, &m, &t, &x);
memset(mp, 0x3f, sizeof mp);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
for (int j = 1; j <= t; ++j)
scanf("%lf", &p[i][j]), p[i][j] /= 100000;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= t << 1; ++j)
if (i == n)
if (j <= t)
f[i][j] = 0;
else
f[i][j] = x;
else
if (j <= t)
f[i][j] = 1e9;
else
f[i][j] = x + mp[i][n];
update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
return 0;
}