topcoder srm 625 div1

problem1 link

假設第$i$種出現的次數為$n_{i}$，總個數為$m$，那么排列數為$T=\frac{m!}{\prod_{i=1}^{26}(n_{i}!)}$

然后計算回文的個數，只需要考慮前一半，得到個數為$R$，那么答案為$\frac{R}{T}$.

為了防止數字太大導致越界，可以分解為質因子的表示方法。

problem2 link

假設終點所在的位置為$(tx,ty)$，那么所有底面是$1x1$的格子$(x,y)$一定滿足$(x-tx)mod(3)=0,(y-ty)mod(3)=0$

把每個這樣的點拆成兩個點然后建立最小割的圖。

源點與所有的$b$相連，終點與匯點相連，流量為無窮，割邊不會在這里產生。

如果不是洞，那么這個格子拆成的兩個點流量為1,表示將這個格子設為洞。

每個格子向周圍連邊，流量為將中間的兩個格子設為洞的代價。

最后最小割就是答案。

problem3 link

首先考慮集合之間的關系。設$f[i][j]$表示前$i$個人分成$j$個集合的方案數。初始化$f[1][1]=n$。那么有：

(1)$f[i+1][j+1]=f[i][j]*j$表示新加一個集合，可以在任意兩個集合之間

(2)$f[i+1][j]=f[i][j]*j*2$表示新加的元素與之前的某一個集合在一起，可以放在那個集合的前后，所以有$j*2$種方法

(３)$f[i+1][j-1]=f[i][j]*j$表示合并兩個集合，可以在任意兩個集合之間插入從而進行合并

最后就是對于$f[x][y]$來說，有多少種方式可以在$n$個位置上放置$x$個使得有$y$個集合并且任意兩個集合不相鄰。令$m=n-(x-y)$，那么相當于在$m$個位置中放置$y$個，使得任意兩個不相鄰。由于$f[1][1]=n$那么這$y$個集合的排列已經計算了，所以現在可以假設這$y$個元素的第一個放在$ｍ$個位置的第一個位置，那么第二個位置也不能放置了。所以還剩$m-2$個位置,$y-1$個元素。由于每放置一個元素其后面的位置就不能放置了，所以可以把剩下$y-1$個元素的位置與其后面相鄰的位置綁定成一個位置，這樣的話，就是$m-2-(y-1)$個位置，$y-1$個元素，即$C_{m-2-(y-1)}^{y-1}=C_{n-(x-y)-2-(y-1)}^{y-1}=C_{n-x-1}^{y-1}$

code for problem1

#include <cmath>
#include <string>
#include <vector>class PalindromePermutations {public:double palindromeProbability(const std::string &word) {std::vector<int> h(26, 0);for (auto e : word) {++h[e - 'a'];}int old_idx = -1;for (int i = 0; i < 26; ++i) {if (h[i] % 2 == 1) {if (old_idx != -1) {return 0.0;}old_idx = i;}}auto total = Compute(h);if (old_idx != -1) {--h[old_idx];}for (auto &e : h) {e /= 2;}auto target = Compute(h);double result = 1.0;for (int i = 2; i < 50; ++i) {result *= std::pow(i, target[i] - total[i]);}return result;}private:std::vector<int> Compute(const std::vector<int> &h) {std::vector<int> result(50, 0);auto Add = [&](int x, int sgn) {for (int i = 2; i <= x; ++i) {int k = i;for (int j = 2; j * j <= k; ++j) {while (k % j == 0) {result[j] += sgn;k /= j;}}if (k != 1) {result[k] += sgn;}}};int n = 0;for (auto e : h) {Add(e, -1);n += e;}Add(n, 1);return result;}
};

code for problem2

#include <limits>
#include <unordered_map>
#include <vector>template <typename FlowType>
class MaxFlowSolver {static constexpr FlowType kMaxFlow = std::numeric_limits<FlowType>::max();static constexpr FlowType kZeroFlow = static_cast<FlowType>(0);struct node {int v;int next;FlowType cap;};public:int VertexNumber() const { return used_index_; }FlowType MaxFlow(int source, int sink) {source = GetIndex(source);sink = GetIndex(sink);int n = VertexNumber();std::vector<int> pre(n);std::vector<int> cur(n);std::vector<int> num(n);std::vector<int> h(n);for (int i = 0; i < n; ++i) {cur[i] = head_[i];num[i] = 0;h[i] = 0;}int u = source;FlowType result = 0;while (h[u] < n) {if (u == sink) {FlowType min_cap = kMaxFlow;int v = -1;for (int i = source; i != sink; i = edges_[cur[i]].v) {int k = cur[i];if (edges_[k].cap < min_cap) {min_cap = edges_[k].cap;v = i;}}result += min_cap;u = v;for (int i = source; i != sink; i = edges_[cur[i]].v) {int k = cur[i];edges_[k].cap -= min_cap;edges_[k ^ 1].cap += min_cap;}}int index = -1;for (int i = cur[u]; i != -1; i = edges_[i].next) {if (edges_[i].cap > 0 && h[u] == h[edges_[i].v] + 1) {index = i;break;}}if (index != -1) {cur[u] = index;pre[edges_[index].v] = u;u = edges_[index].v;} else {if (--num[h[u]] == 0) {break;}int k = n;cur[u] = head_[u];for (int i = head_[u]; i != -1; i = edges_[i].next) {if (edges_[i].cap > 0 && h[edges_[i].v] < k) {k = h[edges_[i].v];}}if (k + 1 < n) {num[k + 1] += 1;}h[u] = k + 1;if (u != source) {u = pre[u];}}}return result;}MaxFlowSolver() = default;void Clear() {edges_.clear();head_.clear();vertex_indexer_.clear();used_index_ = 0;}void InsertEdge(int from, int to, FlowType cap) {from = GetIndex(from);to = GetIndex(to);AddEdge(from, to, cap);AddEdge(to, from, kZeroFlow);}private:int GetIndex(int idx) {auto iter = vertex_indexer_.find(idx);if (iter != vertex_indexer_.end()) {return iter->second;}int map_idx = used_index_++;head_.push_back(-1);return vertex_indexer_[idx] = map_idx;}void AddEdge(int from, int to, FlowType cap) {node p;p.v = to;p.cap = cap;p.next = head_[from];head_[from] = static_cast<int>(edges_.size());edges_.emplace_back(p);}std::vector<node> edges_;std::vector<int> head_;std::unordered_map<int, int> vertex_indexer_;int used_index_ = 0;
};class BlockTheBlockPuzzle {static constexpr int kInfinite = 1000000;public:int minimumHoles(const std::vector<std::string> &S) {MaxFlowSolver<int> solver;int n = static_cast<int>(S.size());int source = -1;int sink = -2;int tx = -1, ty = -1;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (S[i][j] == '$') {tx = i;ty = j;}}}auto P0 = [&](int i, int j) { return i * n + j; };auto P1 = [&](int i, int j) { return i * n + j + n * n; };for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (i % 3 == tx % 3 && j % 3 == ty % 3) {if (S[i][j] == '$') {solver.InsertEdge(P1(i, j), sink, kInfinite);}if (S[i][j] == 'b') {solver.InsertEdge(source, P0(i, j), kInfinite);}if (S[i][j] != 'H') {solver.InsertEdge(P0(i, j), P1(i, j),S[i][j] == '.' ? 1 : kInfinite);}if (i + 3 < n) {auto cost = GetCost(S, i + 1, j, i + 2, j);solver.InsertEdge(P1(i, j), P0(i + 3, j), cost);solver.InsertEdge(P1(i + 3, j), P0(i, j), cost);}if (j + 3 < n) {auto cost = GetCost(S, i, j + 1, i, j + 2);solver.InsertEdge(P1(i, j), P0(i, j + 3), cost);solver.InsertEdge(P1(i, j + 3), P0(i, j), cost);}}}}auto result = solver.MaxFlow(source, sink);if (result >= kInfinite) {return -1;}return result;}private:int GetCost(const std::vector<std::string> &s, int x1, int y1, int x2,int y2) {if (s[x1][y1] == 'b' || s[x2][y2] == 'b') {return kInfinite;}int ans = 0;if (s[x1][y1] == '.') {++ans;}if (s[x2][y2] == '.') {++ans;}return ans;}
};

code for problem3

constexpr int kMod = 1000000007;
constexpr int kMax = 2000;int f[kMax + 1][kMax + 1];
int C[kMax + 1][kMax + 1];class Seatfriends {public:int countseatnumb(int N, int K, int G) {f[1][1] = N;for (int i = 1; i < K; ++i) {for (int j = 1; j <= G; ++j) {long long p = f[i][j];if (p == 0) {continue;}if (j < G) {(f[i + 1][j + 1] += static_cast<int>(p * j % kMod)) %= kMod;}(f[i + 1][j - 1] += static_cast<int>(p * j % kMod)) %= kMod;(f[i + 1][j] += static_cast<int>(p * 2 * j % kMod)) %= kMod;}}if (K == N) {return f[K][0];}C[0][0] = 1;for (int i = 1; i <= N; ++i) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; ++j)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % kMod;}long long ans = 0;for (int j = 1; j <= G; ++j) {ans += static_cast<long long>(f[K][j]) * C[N - K - 1][j - 1] % kMod;}return static_cast<int>(ans % kMod);}
};