problem1 link
定义一个字符串s，定义函数$f(s)=sum_{i=1}^{i<|s|}[s_{i-1} eq s_{i}]$，给定字符串$p,q$，定义函数$g(p,q)=sum_{c='a'}^{c<='z'}count(p,c)*count(q,c)$。其中 $count(s,c)$表示字符$c$在$s$中出现的次数。给定整数N，构造一个包含N个字符串的集合$S$，每个字符串仅有小写字母构成且每个字符串长度不超过100，使得$S$满足$sum_{sin S}f(s)=sum_{p,qin S wedge p eq q}g(p,q)$。右侧计算了$frac{N(N-1)}{2}$对串的$g$值。
假定由w,x,y,z组成的串的长度都是1，那么他们只对$g$有贡献，而剩下的字符每两个构成一个串，且任意两个串不使用同一个字符，那么这些串只对$f$有贡献。
problem2 link
给定一个字符串s，定义$f(i)$表示包含$s_{i}$的子列中回文串的个数。定义$y_{i}=(i+1)*x_{i}%1000000007$。计算所有$y_{i}$的抑或值。
定义$f(L,R)$表示仅由s[L~R]字符组成的回文串的个数，$g(L,R)$表示这样的回文串的个数：回文串的一半由s[0~L]中的字符构成,一半由s[R~|s|]字符组成。$f(L,R)=f(L+1,R)+f(L,R-1)-f(L+1,R-1)[s_{L} eq s_{R}]$,$g(L,R)=g(L-1,R)+g(L,R+1)-g(L-1,R+1)[s_{L} eq s_{R}]$。
$f$的理解方式：$f(L+1,R)=f(L+1,R-1)+{带有R不带有L}$，$f(L,R-1)=f(L+1,R-1)+{带有L不带有R}$，而如果$s_{L} eq s_{R}$，那么$f(L+1,R-1)$就重算了；否则当$s_{L}和s_{R}$都要时的方案还是$f(L+1,R-1)$。这时候不需要减去。$g$的理解类似。
problem3 link
可以用$f[k][i], g[k][i]$表示初始化有$i$个，经过最多$k$轮后得到$b$个的最有策略的概率以及Limak的操作为最优策略的概率．这样需要一个$O(kn^2)$的复杂度．
这里符合最优策略的操作是连续的． 比如对于题目中的第四组数据$(a=10,b=20,k=2)$,有如下的关系：
初始时有$[0, 4]$，在２轮后能够到达20个的最优概率为０
初始时有$[5, 9]$，在２轮后能够到达20个的最优概率为0.25
初始时有$[10, 14]$，在２轮后能够到达20个的最优概率为0.5
初始时有$[15, 19]$，在２轮后能够到达20个的最优概率为0.75
初始时有$[20, oo]$，在２轮后能够到达20个的最优概率为1
这样在dp时，第二维的$n$就可以改为按照区间进行计算．
code for problem1
#include <string>
#include <vector>
class BalancedStrings {
public:
std::vector<std::string> findAny(int N) {
std::vector<std::string> ans;
if (N <= 26) {
for (int i = 0; i < N; ++i) {
std::string s = "";
s += 'a' + i;
ans.push_back(s);
}
return ans;
}
for (int w = 0; w <= N; ++w) {
for (int x = w; w + x <= N; ++x) {
for (int y = x; w + x + y <= N; ++y) {
for (int z = y; w + x + y + z <= N; ++z) {
const int S = F(w) + F(x) + F(y) + F(z);
const int K = N - w - x - y - z;
if (K > 11) {
continue;
}
const int T = (S + 98) / 99;
if (T > K) {
continue;
}
for (int i = 1; i <= w; ++i) {
ans.push_back("w");
}
for (int i = 1; i <= x; ++i) {
ans.push_back("x");
}
for (int i = 1; i <= y; ++i) {
ans.push_back("y");
}
for (int i = 1; i <= z; ++i) {
ans.push_back("z");
}
for (int i = 0, x = 0; i < T; ++i) {
const char c = 'a' + i * 2;
std::string s = "";
s += c;
while (x < S && s.size() < 100) {
(s.size() & 1) ? s += c + 1 : s += c;
++x;
}
ans.push_back(s);
}
char cur = 'v';
while (ans.size() < N) {
std::string s = "";
s += cur;
ans.push_back(s);
--cur;
}
return ans;
}
}
}
}
return ans;
}
private:
int F(int x) { return x * (x - 1) / 2; }
};
code for problem2
#include <string.h>
#include <algorithm>
#include <string>
#include <vector>
class PalindromicSubseq {
static constexpr int kMod = 1000000007;
public:
int solve(const std::string &s) {
int n = static_cast<int>(s.size());
int ans = 0;
std::vector<std::vector<int>> f(n, std::vector<int>(n, -1));
std::vector<std::vector<int>> g(n, std::vector<int>(n, -1));
for (int i = 0; i < n; ++i) {
int t = 0;
for (int j = 0; j < n; ++j) {
if (s[i] != s[j]) {
continue;
}
int ll = std::min(i, j);
int rr = std::max(i, j);
t += Mul(Dfs1(ll + 1, rr - 1, s, &f), Dfs2(ll - 1, rr + 1, s, &g));
t %= kMod;
}
if (t < 0) {
t += kMod;
}
ans ^= Mul(t, i + 1);
}
return ans;
}
private:
int Mul(int a, int b) {
return static_cast<int>(static_cast<int64_t>(a) * b % kMod);
}
int Dfs1(int ll, int rr, const std::string &s,
std::vector<std::vector<int>> *f) {
if (ll > rr) {
return 1;
}
if (ll == rr) {
return 2;
}
int &v = (*f)[ll][rr];
if (v != -1) {
return v;
}
v = (Dfs1(ll + 1, rr, s, f) + Dfs1(ll, rr - 1, s, f)) % kMod;
if (s[ll] != s[rr]) {
v = (v - Dfs1(ll + 1, rr - 1, s, f)) % kMod;
}
return v;
}
int Dfs2(int ll, int rr, const std::string &s,
std::vector<std::vector<int>> *f) {
if (ll < 0 || rr >= static_cast<int>(s.size())) {
return 1;
}
int &v = (*f)[ll][rr];
if (v != -1) {
return v;
}
v = (Dfs2(ll - 1, rr, s, f) + Dfs2(ll, rr + 1, s, f)) % kMod;
if (s[ll] != s[rr]) {
v = (v - Dfs2(ll - 1, rr + 1, s, f)) % kMod;
}
return v;
}
};
code for problem3
#include <string.h>
#include <algorithm>
#include <vector>
class Fraction {
public:
Fraction(int64_t a = 0, int64_t b = 1) : a(a), b(b) {
int64_t t = Gcd(a, b);
a /= t;
b /= t;
if (a == 0) {
b = 1;
}
}
Fraction operator+(const Fraction &other) const {
if (b == other.b) {
return Fraction(a + other.a, other.b);
}
int64_t t = Gcd(b, other.b);
int64_t q = b / t * other.b;
return Fraction(a * (q / b) + other.a * (q / other.b), q);
}
double ToDouble() const { return 1.0 * a / b; }
Fraction Div2() const {
if (a % 2 == 0) {
return Fraction(a / 2, b);
}
return Fraction(a, b * 2);
}
bool operator<(const Fraction &other) const {
return a * other.b < b * other.a;
}
bool operator<=(const Fraction &other) const {
return a * other.b <= b * other.a;
}
bool operator==(const Fraction &other) const {
return a * other.b == b * other.a;
}
private:
int64_t Gcd(int64_t a, int64_t b) const { return b == 0 ? a : Gcd(b, a % b); }
int64_t a;
int64_t b;
};
class OptimalBetting {
public:
double findProbability(int a, int b, int k) {
std::vector<std::vector<double>> dp(2, std::vector<double>(b * 2 + 1, 1.0));
std::vector<std::pair<Fraction, int>> split;
split.emplace_back(0, 0);
split.emplace_back(1, b);
// Add sentry to simplfy implemention
split.emplace_back(0, b * 2 + 1);
for (int i = 1; i <= k; ++i) {
split = Solve(split, b, &(dp[(i & 1) ^ 1]), &(dp[i & 1]));
}
return dp[k & 1][a];
}
private:
std::vector<std::pair<Fraction, int>> Solve(
const std::vector<std::pair<Fraction, int>> &last_split, int b,
std::vector<double> *last, std::vector<double> *curr) {
for (int i = 1; i <= b * 2; ++i) {
(*last)[i] += (*last)[i - 1];
}
auto Get = [&](int l, int r) -> double {
if (l > r) {
return 0;
}
return l == 0 ? (*last)[r] : (*last)[r] - (*last)[l - 1];
};
std::vector<std::pair<Fraction, int>> curr_split;
curr_split.emplace_back(0, 0);
(*curr)[0] = 1;
for (int i = 1; i < b; ++i) {
size_t left = 0, right = 1;
for (size_t j = 1; j < last_split.size(); ++j) {
if (last_split[j].second > i) {
left = j - 1;
right = j;
break;
}
}
Fraction maxp;
(*curr)[i] = 0;
while (right < last_split.size()) {
int upper = std::min(i - last_split[left].second,
last_split[right].second - i - 1);
int lower = left + 1 <= right - 1
? std::max(i - last_split[left + 1].second + 1,
last_split[right - 1].second - i)
: 0;
Fraction rp =
(last_split[left].first + last_split[right - 1].first).Div2();
if (maxp <= rp) {
double p = Get(i - upper, i - lower) / (i + 1) / 2 +
Get(i + lower, i + upper) / (i + 1) / 2;
if (rp == maxp) {
(*curr)[i] += p;
} else {
(*curr)[i] = p;
}
maxp = rp;
}
if (last_split[left].second == i - upper) {
if (left == 0) {
break;
}
left--;
}
if (last_split[right].second == i + upper + 1) {
right++;
}
}
if (curr_split.back().first < maxp) {
curr_split.emplace_back(maxp, i);
}
}
for (int i = b; i <= b * 2; ++i) {
(*curr)[i] = 1;
}
curr_split.emplace_back(1, b);
curr_split.emplace_back(0, b * 2 + 1);
return curr_split;
}
};