@Falsyta 2015-09-25T07:56:29.000000Z 字数 19327 阅读 2353

TCO 2013

OI TCO Topcoder

Level 3

虽然好累但是总算是写完了……
感觉老是看题解也不是事……还是去写写Level 1,2去放松下吧……

TCO13 Round 1A DirectionBoard

……注意到合法解应该是每个点出入度都为1。
然后建二分图就是最小权匹配了。

# include <cstdio>
# include <cstring>
# include <algorithm>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
using namespace std;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
template <class T0, class T1> bool RlxN (T0 &a, T1 b) {if (a > b) return a = b, true; return false;}
template <class T0, class T1> bool RlxX (T0 &a, T1 b) {if (a < b) return a = b, true; return false;}
const int inf = 1 << 30;
# define P(i, j) ((i) * m + (j) + 1)
# define PR 400
class DirectionBoard
{
private:
    int ord[400];
    int g[PR][PR], lx[PR], ly[PR], match[PR], lack, N;
    bool visx[PR], visy[PR];
    bool Find (int x)
    {
        visx[x] = true; int t;
        REP (y, N)
        {
            if (visy[y]) continue;
            t = lx[x] + ly[y] - g[x][y];
            if (t == 0)
            {
                visy[y] = true;
                if (match[y] == -1 || Find (match[y]))
                    return match[y] = x, true;
            }
            else RlxN (lack, t);
        }
        return false;
    }
    int KM ()
    {
        RST (lx), RST (ly), CLR (match, -1);
        REP (i, N) REP (j, N) RlxX (lx[i], g[i][j]);
        REP (x, N)
        {
            while (true)
            {
                RST (visx), RST (visy), lack = inf;
                if (Find (x)) break;
                REP (i, N) 
                {
                    if (visx[i]) lx[i] -= lack; 
                    if (visy[i]) ly[i] += lack;
                }
            }
        }
        int ans = 0;
        REP (i, N) ans += g[match[i]][i];
        return ans;
    }
public:
    int getMinimum (vector <string> board)
    {
        int n = board.size (), m = board[0].length ();
        ord['U'] = 0, ord['D'] = 1, ord['L'] = 2, ord['R'] = 3;
        N = n * m;
        REP (i, N) REP (j, N) g[i][j] = - 10000; 
        REP_0 (i, n)
        {
            REP_0 (j, m)
            {
                int _d = ord[board[i][j]];
                REP_0 (d, 4)
                {
                    int mx = (i + dx[d] + n) % n, my = (j + dy[d] + m) % m;
                    RlxX (g[P (i, j)][P (mx, my)], - (d != _d));
                }
            }
        }
        return - KM ();
    }
};

TCO13 Round 1B EllysReversals

如果没有翻转前缀长度为偶数的限制则显然可以将串 $s$ 中的字母任意排列。
加上限制也只不过是 $2i+1$ 位要和 $2i+2$ 位相邻而已（最后一位特殊处理）。

# include <cstdio>
# include <algorithm>
# include <iostream>
# include <string>
# include <cstring>
# include <set>
using namespace std;
class EllysReversals
{
private:
    set <string> strSet;
    string transform (string word)
    {
        string result;
        vector <pair <char, char> > temp;
        for (int i = 0; i < word.length (); i ++)
        {
            if (i % 2 == 0) continue;
            char a = word[i - 1], b = word[i];
            if (a > b) swap (a, b);
            temp.push_back (make_pair (a, b));
        }
        sort (temp.begin (), temp.end ());
        for (int i = 0; i < temp.size (); i ++)
            result.push_back (temp[i].first), result.push_back (temp[i].second);
        if (word.length () % 2 == 1)
            result.push_back (word[word.length () - 1]);
        return result;
    }
public:
    int getMin (vector <string> words)
    {
        for (int i = 0; i < words.size (); i ++)
        {
            string str = transform (words[i]);
            if (strSet.find (str) != strSet.end ())
                strSet.erase (str);
            else
                strSet.insert (str);
        }
        return (int) strSet.size ();
    }
};

TCO13 Round 1C TheKnights

似乎忘了贴上的样子……
计算每个点被攻击到的概率就好了，然后就是大暴力嘛……
似乎当时着急回去上课把代码写得乱七八糟的……

# include <cstdio>
# include <cassert>
# include <iostream>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
typedef double dd;
typedef long double ld;
ld max (ld a, ld b, ld c) {return max (a, max (b, c));}
ld min (ld a, ld b, ld c) {return min (a, min (b, c));}
class TheKnights
{
private:
    double solve0 (ld n, ld a)
    {
        ld dx[] = {-a, -a, 0,  a,  a};
        ld dy[] = {-a,  a, 0, -a,  a};
        ld N = n * n;
        ld t0 = 0, t1 = 0;
        REP_0 (d, 5)
        {
            ld _x = dx[d], _y = dy[d];
            t0 += max ((ld) 0, min (n, n - _x) - max ((ld) 1, 1 - _x) + 1) * max ((ld) 0, min (n, n - _y) - max ((ld) 1, 1 - _y) + 1); 
        }
        REP_0 (d0, 5)
            FOR (d1, d0 + 1, 4)
            {
                ld _x = dx[d0], __x = dx[d1], _y = dy[d0], __y = dy[d1];
                t1 += max ((ld) 0, min (n, n - _x, n - __x) - max ((ld) 1, 1 - _x, 1 - __x) + 1) * max ((ld) 0, min (n, n - _y, n - __y) - max ((ld) 1, 1 - _y, 1 - __y) + 1); 
            }
        return (dd) (2 * t0 / N - t1 * 2 / N / (N - 1));
    }
public:
    double find (int _n, int _a, int _b)
    {
        if (_a == _b) return solve0 ((ld) _n, (ld) _a);
        ld n = _n;
        ld a = _a, b = _b;
        ld dx[] = {-b, -b, -a, -a,  0,  a,  a,  b,  b};
        ld dy[] = {-a,  a, -b,  b,  0, -b,  b, -a,  a};
        ld N = n * n;
        ld t0 = 0, t1 = 0;
        REP_0 (d, 9)
        {
            ld _x = dx[d], _y = dy[d];
            t0 += max ((ld) 0, min (n, n - _x) - max ((ld) 1, 1 - _x) + 1) * max ((ld) 0, min (n, n - _y) - max ((ld) 1, 1 - _y) + 1); 
        }
        REP_0 (d0, 9)
            FOR (d1, d0 + 1, 8)
            {
                ld _x = dx[d0], __x = dx[d1], _y = dy[d0], __y = dy[d1];
                t1 += max ((ld) 0, min (n, n - _x, n - __x) - max ((ld) 1, 1 - _x, 1 - __x) + 1) * max ((ld) 0, min (n, n - _y, n - __y) - max ((ld) 1, 1 - _y, 1 - __y) + 1); 
            }
        return (dd) (2 * t0 / N - t1 * 2 / N / (N - 1));
    }
};

TCO13 Round 2A ThePowers

然而不对着题解估计还是写不出来…………
考虑将可能算重的 $X$ 化为 $g^k$ 。
对于每个可能的 $g$ ，考虑算不同的 $g^{kY}$ 的个数。
显然不同的 $g$ 之间相互独立，则转化为 $k\in [1,log_gA], Y\in [1,B]$ 的不同的 $kY$ 个数。
容斥计算，为了方便计算可以将 $kY$ 的取值分成 $[1,log_gA]$ 段计算，每一段计算 $((i-1)B,iB]$ 的个数。

# include <cstdio>
# include <cstring>
# include <cassert>
# include <algorithm>
# include <iostream>
using namespace std;
typedef long long ll;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define CLR(a, x) memset (a, x, sizeof (a))
class ThePowers
{
private:
    int pl[100], psz;
    int bitc[1 << 15], dn[1 << 15];
    ll rec[50], lcm[1 << 15];
    template <class T> T gcx (T a, T b) 
    {
        if (a < b) swap (a, b);
        return !b ? a : gcx (b, a % b);
    }
    bool check (int n)
    {
        int d = -1;
        for (int i = 2; i * i <= n; i ++)
        {
            if (n % i != 0) continue;
            int q = 0;
            while (n % i == 0) n /= i, q ++;
            if (d == -1) d = q;
            else d = gcx (d, q);
        }
        if (n > 1) return true;
        else return d == 1;
    }
    ll calc (ll L, ll R)
    {
        int M = 1 << psz;
        ll res = 0;
        lcm[0] = 1;
        REP (s, M - 1)
        {
            lcm[s] = lcm[s - (s & -s)] * pl[dn[s & -s]] / gcx (lcm[s - (s & -s)], (ll) pl[dn[s & -s]]);
            if (bitc[s] & 1) res += R / lcm[s] - L / lcm[s];
            else res -= R / lcm[s] - L / lcm[s];
        }
        return res;
    }
    ll solve (int n, int m)
    {
        if (rec[n] != -1) return rec[n];
        ll &s = rec[n]; s = 0;
        REP (i, n)
        {
            psz = 0;
            FOR (j, i, n)
            {
                bool succ = true;
                FOR (k, i, j - 1) if (j % k == 0) {succ = false; break;}
                if (succ) pl[++ psz] = j;
            }
            s += calc (1ll * (i - 1) * m, 1ll * i * m);
        }
        return s;
    }
public:
    ll find (int n, int m)
    {
        int _s = sqrt (n), M = 1 << 15;
        CLR (rec, -1);
        ll ans = m - 1;
        REP (i, M - 1) bitc[i] = bitc[i - (i & - i)] + 1;
        REP_0 (i, 15) dn[1 << i] = i + 1;
        FOR (i, 2, _s)
        {
            if (!check (i)) continue;
            int q = 0, t = 1;
            while (1ll * t * i <= n) t *= i, q ++;
            ans += 1ll * q * m - solve (q, m);
        }
        return 1ll * n * m - ans;
    }
};

TCO 2013 Round 2B LitPanels

考虑枚举一个长方形卡住它。
剩下的就是分类讨论大暴力了。
虽然不知道题解为什么写的是容斥……
时间复杂度 $O(N^2)$ 。

# include <cstdio>
# include <cassert>
# include <iostream>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
const int P = 1000000007;
class LitPanels
{
private:
    int n, m, a, b;
    int pw2[2000];
    int calc (int sq)
    {
        int res = 0;
        REP_0 (s, 4)
        {
            int cnt = (s >> 1 & 1) + (s & 1), _q = sq, tmp = 1;
            REP (t, 2 - cnt) _q -= a + b - 2, tmp = 1ll * tmp * (pw2[a - 1] + P - 1) % P * (pw2[b - 1] + P - 1) % P;
            res = (res + 1ll * tmp * pw2[_q]) % P;
        }
        return res;
    }
    int calc0 (int sq, int x, int y)
    {
        int res = 0;
        REP_0 (s, 16)
        {
            bool c0 = s & 1, c1 = s >> 1 & 1, c2 = s >> 2 & 1, c3 = s >> 3;
            int tmp = 1, _q = sq;
            if (!c0 && !c3) tmp = 1ll * tmp * (pw2[x - 2] + P - 1) % P, _q -= x - 2;
            if (!c1 && !c2) tmp = 1ll * tmp * (pw2[x - 2] + P - 1) % P, _q -= x - 2;
            if (!c0 && !c1) tmp = 1ll * tmp * (pw2[y - 2] + P - 1) % P, _q -= y - 2;
            if (!c2 && !c3) tmp = 1ll * tmp * (pw2[y - 2] + P - 1) % P, _q -= y - 2;
            res = (res + 1ll * tmp * pw2[_q]) % P;
        }
        return res;
    }
public:
    int countPatterns (int _n, int _m, int _a, int _b)
    {
        n = _n, m = _m, a = _a, b = _b;
        int ans = 1;
        pw2[0] = 1;
        REP (i, n * m) pw2[i] = (pw2[i - 1] << 1) % P;
        REP (i, n)
            REP (j, m)
            {
                int res = 0;
                if (i == 1 && j == 1) res = 1;
                else if (i == 1) res = pw2[min (j, b * 2) - 2];
                else if (j == 1) res = pw2[min (i, a * 2) - 2];
                else if (i <= a || j <= b) res = calc0 (min (a * 2, i) * min (b * 2, j) - 4, min (a * 2, i), min (b * 2, j));
                else if (a < i && i < a * 2 && b < j && j < b * 2)
                {
                    res = calc (i * j - 2 * (i - a) * (j - b) - 2) << 1;
                    if (res >= P) res -= P;
                    int _a = (a << 1) - i, _b = (b << 1) - j,
                        ta = pw2[_a] + P - 1, 
                        tb = pw2[_b] + P - 1, 
                        tc = pw2[_a * j + _b * i - _a * _b - _a * 2 - _b * 2];
                    if (ta >= P) ta -= P; if (tb >= P) tb -= P;
                    res -= 1ll * ta * ta % P * tb % P * tb % P * tc % P;
                    if (res >= P) res -= P;
                    if (res < 0) res += P;
                }
                else if (i >= a * 2 || j >= b * 2) {res = calc (a * b * 2 - 2) << 1; if (res >= P) res -= P;}
                else assert (0);
                ans = (ans + 1ll * (n - i + 1) * (m - j + 1) * res) % P;
            }
        return ans;
    }
};

TCO13 Round 2C WellTimedSearch

…………显然枚举第 $i$ 层节点就好了……

# include <cstdio>
# include <algorithm>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_D(i, n) for (int i = n; i >= 1; i --)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
using namespace std;
typedef double dd;
class WellTimedSearch
{
public:
    double getProbability (int n, int l, int r)
    {
        dd ans = 0;
        REP (i, n)
        {
            int t = i, rem = n - i, wst = 0;
            REP_D (j, l - 1) 
            {
                t = (t + 1) >> 1; 
                if (t == 1) {rem -= j, wst += j; break;}
                rem -= t, wst += t;
            }
            if (t != 1 || rem < 0) return ans;
            t = i;
            FOR (j, l + 1, r)
            {
                t <<= 1, rem -= min (rem, t);
                if (!rem) break;
            }
            wst += rem;
            ans = max (ans, (dd) (n - wst) / n);
        }
        return ans;
    }
};

TCO 2013 Round 3A TrickyInequality

似乎这是TCO13最难的题了……

太可怕了…………
我们从头来。
为了方便在这里贴出用到的公式：

x n - = \sum k = 0 n (- 1) n - k [n k] x k (1)

$\begin{equation}x^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n-k}\left[{n\atop k}\right]x^k\end{equation}$

x n = \sum k {n k} x k - (2)

$\begin{equation}x^n=\sum_k\left\{{n\atop k}\right\}x^{\underline k}\end{equation}$

Δ n f (x) = \sum i = 0 d c i (x i - n) 其 中 f (x) = \sum i = 0 d c i (x i) (3)

$\begin{equation}\Delta^nf(x)=\sum_{i=0}^dc_i\binom{x}{i-n}\text{其中}f(x)=\sum_{i=0}^dc_i\binom{x}{i}\end{equation}$

考虑容斥，显然答案为 $\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{s-kt}{m}$
$(-1)^k\binom{n}{k}$ 不好化简，我们考虑 $n$ 阶差分，显然有

Δ n f (x) = \sum k = 0 n (- 1) n - k (n k) f (x + k)

$\Delta^nf(x)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(x+k)$
稍加处理就得到我们需要的形式，令

f(x)=(s−xtm) $f(x)=\binom{s-xt}{m}$ ，所求即

Δnf(0) $\Delta^nf(0)$ ：
对差分的常用技巧是将其转化为牛顿级数，我们先试图将

f(x) $f(x)$ 转化成一个多项式，然后再转化成牛顿级数。
下降幂可以用斯特林数很容易地转化成多项式（公式 (1)）：

(s - x t m) = 1 m ! \sum j = 0 m x j \sum i = j m (- 1) m - i + j (i j) [m i] t j s i - j

$\binom{s-xt}{m}=\frac{1}{m!}\sum_{j=0}^{m}x^j\sum_{i=j}^{m}(-1)^{m-i+j}\binom{i}{j}\left[{m\atop i}\right]t^js^{i-j}$
继续转化多项式（利用公式(2)），令多项式中

xi $x^i$ 的系数为

ai $a_i$ 。

\sum i = 0 m a i x i = \sum j = 0 m (x j) \sum i = j m a i {i j} j!

$\sum_{i=0}^{m}a_ix^i=\sum_{j=0}^{m}\binom{x}{j}\sum_{i=j}^{m}a_i\left\{ {i \atop j}\right\} j!$

于是得到牛顿级数，令 $\binom{x}{i}$ 的系数为 $b_i$ ，则 $b_n$ 为所求（公式(3)）。
将 $a_i$ 代入，最终得到：

\sum k = 0 n (- 1) k (n k) (s - k t m) = n ! ( - 1 ) n + m t n m ! \sum i = 0 m - n \sum j = 0 m - n - i (- 1) j (n + i + j j) {n + i n} [m n + i + j] t i s j

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} \binom{s-kt}{m}=\frac{n!(-1)^{n+m} t^n}{m!} \sum_{i=0}^{m-n} \sum_{j=0}^{m-n-i} (-1)^j \binom{n+i+j}{j} \left\{ {n+i \atop n}\right\} \left[{m\atop n+i+j}\right] t^i s^j$

最后只剩下计算快速斯特林数的问题了，注意到有 $n+i-n\leq 100, m-n-i-j\leq 100$ 。
我们考虑斯特林数的组合意义。
第二类斯特林数表示将 $n$ 个元素分为 $k$ 个非空子集的方案数。
容易发现至多只有 $n-k$ 个子集的大小大于 $1$ 。
我们暴力枚举大于 $1$ 的子集个数，则有：

{n k} = \sum i = 0 n - k (n n - k + i) g (n - k + i, i)

$\left\{ {n \atop k}\right\}=\sum_{i=0}^{n-k}\binom{n}{n-k+i}g(n-k+i,i)$
其中

g(n,k) $g(n,k)$ 为将

n $n$ 个元素分为

k $k$ 个大小大于

1 $1$ 的子集的方案数。
考虑第

n $n$ 个元素要么与此前一个元素一起成为一个新集合，要么加入之前的集合，则有

g(n,k)=kg(n−1,k)+(n−1)g(n−2,k−1) $g(n,k)=kg(n-1,k)+(n-1)g(n-2,k-1)$

第一类斯特林数表示将 $n$ 个元素分为 $k$ 个非空环排列的方案数。
类似第二类斯特林数，有

[n k] = \sum i = 0 n - k (n n - k + i) f (n - k + i, i)

$\left[{n\atop k}\right]=\sum_{i=0}^{n-k}\binom{n}{n-k+i}f(n-k+i,i)$
其中

g(n,k) $g(n,k)$ 为将

n $n$ 个元素分为

k $k$ 个大小大于

1 $1$ 的环排列的方案数。
我们用一个序列表示这些环排列，每个环排列我们令其中最小的元素排在第一个，排列之间用一个特殊元素分割，考虑第

n $n$ 个元素要么与此前一个元素一起成为一个新环排列，要么插入之前的环排列构成的序列，则有：

f(n,k)=(n−1)f(n−1,k)+(n−1)f(n−2,k−1) $f(n,k)=(n-1)f(n-1,k)+(n-1)f(n-2,k-1)$

因此最终复杂度为 $O((m-n)^2)$ 。

太可怕了…………

# include <cstdio>
# include <cassert>
# include <iostream>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
typedef long long ll;
# define P 1000000007
# define NR 500
class TrickyInequality
{
private:
    int f[NR][NR], g[NR][NR], stir1[NR], stir2[NR], iv[NR];
    int n, m;
    inline int Pow (int a, int z)
    {
        int s = 1;
        do {if (z & 1) s = 1ll * s * a % P; a = 1ll * a * a % P;} while (z >>= 1);
        return s;
    }
    inline int inv (int x) {return x <= 4 * (n - m) + 10 ? iv[x] : Pow (x, P - 2);}
    int calc (int n, int m, int a[NR][NR])
    {
        int res = 0, _bi = 1;
        REP (i, n - m) _bi = 1ll * _bi * (n - i + 1) % P * inv (i) % P;
        REP_0N (i, n - m)
        {
            res = (res + 1ll * a[n - m + i][i] * _bi) % P;
            _bi = 1ll * _bi * (m - i) % P * inv (n - m + i + 1) % P;
        }
        return res;
    }
    void init (int n, int a, int b)
    {
        REP (i, n) iv[i] = Pow (i, P - 2);
        f[0][0] = g[0][0] = 1;
        REP (i, n)
            REP (j, n)
            {
                f[i][j] = 1ll * f[i - 1][j] * (i - 1) % P;
                g[i][j] = 1ll * g[i - 1][j] * j % P;
                if (i > 1)
                    f[i][j] = (f[i][j] + 1ll * f[i - 2][j - 1] * (i - 1)) % P, 
                    g[i][j] = (g[i][j] + 1ll * g[i - 2][j - 1] * (i - 1)) % P;
            }
        REP_0N (i, n) stir1[i] = calc (b, a + i, f);
        REP_0N (i, n) stir2[i] = calc (a + i, a, g);
    }
public:
    int countSolutions (ll s, int t, int _n, int _m)
    {
        n = _n, m = _m, s %= P;
        init ((m - n) * 2 + 10, n, m);
        int _a = Pow (t, n);
        FOR (i, n + 1, m) _a = 1ll * _a * inv (i) % P;
        if ((n + m) % 2 == 1) _a = P - _a;
        int _tp = 1, res = 0;
        REP_0N (i, m - n)
        {
            int _si = 1, _sp = 1, _bi = 1, tmp = 0;
            REP_0N (j, m - n - i)
            {
                tmp = (tmp + 1ll * _si * _bi % P * stir1[i + j] % P * _sp) % P;
                _bi = 1ll * _bi * (n + i + j + 1) % P * inv (j + 1) % P;
                _sp = 1ll * _sp * s % P;
                _si = P - _si;
            }
            res = (res + 1ll * tmp * stir2[i] % P * _tp) % P;
            _tp = 1ll * _tp * t % P;
        }
        return 1ll * res * _a % P;
    }
};

TCO 2013 Round 3B ToastJumping

考虑一个向量的时候 $f(x)=\lfloor\sqrt{D-x^2}\rfloor$ 上的整点构成的凸壳。
可以证明 $N$ 个向量的时候凸壳是与1个向量时相似的。
我的民科证法是
考虑对于一个凸壳上的点 $P$ ，不存在凸壳上异于 $P$ 的点 $A, B$ ，使得 $\overrightarrow{OA}+\overrightarrow{OB}$ 与 $OP$ 共线且， $|\overrightarrow{OA}+\overrightarrow{OB}|>2|\overrightarrow{OP}|$ ，画一画似乎可以发现因为是凸的所以显然……

# include <cstdio>
# include <cmath>
# include <iostream>
# include <algorithm>
# include <vector>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair <int, int> poi;
const ll lnf = 1ll << 61;
class ToastJumping
{
private:
    poi po[1000000];
    int pl;
# define _x first
# define _y second
    ll proc (ll a, ld b) {if (a - b > 0.99999999) return a - 1; return a;}
    inline bool check (poi a, poi b, poi c) {return 1ll * (b._x - a._x) * (c._y - a._y) >= 1ll * (c._x - a._x) * (b._y - a._y);}
    int solve (int X, int Y, int D)
    {
        int s = sqrt (D + 0.000001);
        pl = 0;     
        REP_0N (x, s)
        {
            poi t = make_pair (x, (int) (sqrt (D - x * x) + 0.00001));
            while (pl >= 2 && check (po[pl - 1], po[pl], t)) pl --;
            po[++ pl] = t;
        }
        ll ans = lnf;
        REP (i, pl - 1)
        {
            ld k = (ld) (po[i + 1].second - po[i].second) / (po[i + 1].first - po[i].first), b = po[i].second - po[i].first * k;
            ll _l = max (1ll * (X + po[i + 1].first - 1) / po[i + 1].first, proc (ceil ((Y - k * X) / b), (Y - k * X) / b)), _r = lnf;
            if (po[i].first > 0) _r = min (_r, 1ll * X / po[i].first);
            if (_l <= _r) ans = min (ans, _l);
        }
        return (int) ans;
    }
public:
    vector <int> minJumps (vector <int> x, vector <int> y, vector <int> d)
    {
        vector <int> answer;
        for (int i = 0; i < x.size (); i ++) answer.push_back (solve (abs (x[i]), abs (y[i]), d[i]));
        return answer;
    }
};

TCO 2013 Semifinal 1 GameWithTree

首先这个博弈状态形成DAG是显然的。
…………考虑全白的子树强制第一步选根的 $SG$ 值为 $2^d$ （ $d$ 为子树最大深度）。
黑点显然是各儿子子树 $SG$ 值的异或和。
考虑根为白点的子树。
结论：根为白点的子树的 $SG$ 值为各儿子子树 $SG$ 值的异或和再异或 $2^d$ 。

证明：
考虑利用 $SG$ 函数的定义用数学归纳法证明。

假设我们正在证明某个“各儿子子树 $SG$ 值的异或和再异或 $2^d$ ”的值为 $S$ 的状态，且其后继状态都已被证明。

（对于根被选中的后继状态显然是对的）

令“各儿子子树 $SG$ 值的异或和”为 $T$ 。
考虑根未被选中的状态。
对于 $0\leq X<2^d$ 的 $SG$ 值 $X$ 显然可以选根得到。
对于 $2^d\leq X<S$ 的 $SG$ 值 $X$ ，我们可以将根忽略不计，只在儿子中进行操作。
因此对于 $0\leq X<S$ 的状态都可以被达到。

下面证明 $SG$ 值 $S$ 不能被达到。
假设可以达到某状态 $Z$ ，其 $SG$ 值为 $S$ 。
由于状态 $Z$ 可以被到达，所以对于状态 $Z$ 结论是对的。
则状态 $Z$ 中根必然未被选中，因为容易得到 $T<2^d$ ，
于是我们将状态 $Z$ 中的根去掉得到状态 $Z'$ ，可知 $Z'$ 的 $SG$ 值为 $T$ ，显然违反了 $SG$ 的定义。

证毕。（好民科啊T_T………………

算了应该是对的……

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
using namespace std;
struct Edge {int y, frt; void Set (int yr, int fr) {y = yr, frt = fr;}};
typedef long long ll;
# define v g[i].y
# define NR 1000
class GameWithTree
{
private:
    Edge g[NR];
    int pos[NR], dep[NR], gsz;
    ll f[NR];
    bool col[NR];
    void AE (int x, int y) {g[++ gsz].Set (y, pos[x]), pos[x] = gsz;}
    void DFS (int x)
    {
        for (int i = pos[x]; i; i = g[i].frt)
        {
            DFS (v);
            dep[x] = max (dep[x], dep[v]);
            f[x] ^= f[v];
        }
        if (!col[x]) f[x] ^= 1ll << dep[x];
        dep[x] ++;
    }
public:
    string winner (vector <int> parent, string color)
    {
        for (int i = 0; i < parent.size (); i ++)
            AE (parent[i] + 1, i + 2);
        for (int i = 0; i < color.length (); i ++)
            col[i + 1] = color[i] == 'B';
        string answer;
        DFS (1);
        if (f[1] > 0) answer = "Masha";
        else answer = "Petya";
        return answer;
    }
};

TCO 2013 Semifinal 2 OneBlack

可以发现无障碍的话就是要求一个把左上和右下隔开的方案。
有障碍的话把障碍缩点，统计左下到右上的路径就好。
一手贱把 $O(N^2)$ 写成 $O(N^4)$ 了……

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cassert>
# include <string>
# include <vector>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
int dx[] = {-1, -1, -1,  0,  0,  1,  1,  1};
int dy[] = {-1,  0,  1, -1,  1, -1,  0,  1};
# define NR 60
# define PR 2000
# define P 1000000007
class OneBlack
{
private:
    int f[PR], in[PR], q[PR], S, T;
    int n, m, col[NR][NR], csz;
    bool v1[NR][NR], v2[NR][NR], del[NR][NR], mp[NR][NR], g[PR][PR];
    inline void AE (int x, int y) {if (!g[x][y]) in[y] ++, g[x][y] = true;}
    inline int poi (int x, int y)
    {
        if (x < 1 || x > n || y < 1 || y > m) return -1;
        return (x - 1) * m + y;
    }
    void dfs1 (int x, int y) {if (poi (x, y) == -1 || v1[x][y] || mp[x][y]) return ; v1[x][y] = 1, dfs1 (x + 1, y), dfs1 (x, y + 1);}
    void dfs2 (int x, int y) {if (poi (x, y) == -1 || v2[x][y] || mp[x][y]) return ; v2[x][y] = 1, dfs2 (x - 1, y), dfs2 (x, y - 1);}
    void dfs3 (int x, int y, int c)
    {
        if (poi (x, y) == -1 || col[x][y] || !del[x][y]) return ;
        col[x][y] = c; REP_0 (d, 8) dfs3 (x + dx[d], y + dy[d], c);
    }
    int Topo ()
    {
        int h = 1, t = 0, N = 2 * n * m + 2;
        q[++ t] = S, f[S] = 1;
        while (h <= t)
        {
            int x = q[h ++];
            REP (v, N)
            {
                if (!g[x][v]) continue;
                f[v] += f[x]; if (f[v] >= P) f[v] -= P;
                if (!(-- in[v])) q[++ t] = v;
            }
        }
        return f[T];
    }
    inline int gridId (int i, int j) {return del[i][j] ? col[i][j] : (csz + poi (i, j));}
public:
    int countColorings (vector <string> grid)
    {
        n = grid.size (), m = grid[0].length (), S = 2 * n * m + 1, T = 2 * n * m + 2;
        int _a = 1;
        REP (i, n) REP (j, m) mp[i][j] = grid[i - 1][j - 1] == '#';
        dfs1 (1, 1), dfs2 (n, m);
        REP (i, n) REP (j, m) del[i][j] = !v1[i][j] || !v2[i][j] || mp[i][j];
        REP (i, n) REP (j, m) if (!col[i][j] && del[i][j]) dfs3 (i, j, ++ csz);
        REP (i, n) 
        {
            if (del[i][1] || !del[i + 1][1]) AE (S, gridId (i, 1)); 
            if (del[i][m] || !del[i - 1][m]) AE (gridId (i, m), T);
        }
        REP (i, m) 
        {
            if (del[1][i] || !del[1][i + 1]) AE (gridId (1, i), T); 
            if (del[n][i] || !del[n][i - 1]) AE (S, gridId (n, i));
        }
        REP (i, n)
            REP (j, m)
            {
                int x = poi (i, j);
                if (del[i][j])
                {
                    int y = poi (i - 1, j);
                    if (y != -1 && !del[i - 1][j]) AE (col[i][j], csz + y);
                    y = poi (i, j + 1);
                    if (y != -1 && !del[i][j + 1]) AE (col[i][j], csz + y);
                    y = poi (i - 1, j + 1);
                    if (y != -1 && !del[i - 1][j + 1]) AE (col[i][j], csz + y);
                    if (!mp[i][j]) {_a = _a << 1; if (_a >= P) _a -= P;}
                }
                else
                {
                    int y = poi (i - 1, j + 1);
                    if (y != -1) 
                    {
                        if (del[i - 1][j + 1]) AE (csz + x, col[i - 1][j + 1]);
                        else if (!del[i - 1][j] && !del[i][j + 1]) AE (csz + x, csz + y);
                    }
                    y = poi (i - 1, j);
                    if (y != -1 && del[i - 1][j]) AE (csz + x, col[i - 1][j]);
                    y = poi (i, j + 1);
                    if (y != -1 && del[i][j + 1]) AE (csz + x, col[i][j + 1]);
                }
            }   
        return 1ll * _a * Topo () % P;
    }
};

TCO 2013 Wildcard SemiMultiple

本来打算写强行DP搞的……写了三节课以后还是决定弃疗写“循环逆卷积（雾）？”……
反正就是想办法把可以改的位抠出来……
目前还不知道为什么这是对的…………
休息去想想……

# include <cstdio>
# include <cstring>
# include <iostream>
# include <cassert>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define Mo(a) if ((a) >= 1000000007) a -= 1000000007;
# define RST(a) memset (a, 0, sizeof (a))
# define mod 1000000007
# define NR 2010
class SemiMultiple
{
private:
    int bi[NR][NR], f[NR][NR], pw[NR], cnt[NR], g[NR], tv[NR];
    int n, m;
    void inv (int t)
    {
        int sum = 0;
        REP_0 (i, m) {sum += g[i]; Mo (sum);}
        if (sum % 2 == 1) sum = (sum + mod) / 2;
        else sum >>= 1;
        for (int i = 1; i < m; i += 2) {sum += mod - g[(i + 1) * t % m]; Mo (sum);}
        tv[0] = sum;
        REP_0 (i, m - 1) tv[(i + 1) * t % m] = (g[(i + 1) * t % m] - tv[i * t % m] + mod) % mod;
        REP_0 (i, m) g[i] = tv[i];  
    }
    int solve ()
    {
        bi[0][0] = f[0][0] = pw[0] = 1;
        REP (i, n) 
        {
            pw[i] = pw[i - 1] * 2 % m, cnt[pw[i - 1]] ++, bi[i][0] = 1;
            REP (j, n) {bi[i][j] = bi[i - 1][j - 1] + bi[i - 1][j]; Mo (bi[i][j]);}
        }
        REP (i, n) REP_0 (j, m) {f[i][j] = f[i - 1][j] + f[i - 1][(j - pw[n - i] + m) % m]; Mo (f[i][j]);}
        if (m == 1) return 0;
        if (n <= 0) return 0;
        if (n == 1) return 1;
        int res = 0;
        REP (i, m - 1)
        {
            if (!cnt[i] && !cnt[m - i]) continue;
            REP_0 (j, m) g[j] = f[n][j];
            REP (j, cnt[i]) inv (i);
            REP (j, cnt[m - i]) inv (m - i);
            REP_0N (c0, cnt[i])
                REP_0N (c1, cnt[m - i])
                {
                    if (!c0 && c1 == cnt[m - i]) continue;
                    res = (res + 1ll * bi[cnt[i]][c0] * bi[cnt[m - i]][c1] % mod * g[(i - c0 * i % m - c1 * (m - i) % m + m + m) % m]) % mod;
                }
        }
        return res;
    }
public:
    int count (int _n, int _m)
    {
        int t = 0;
        while (_m % 2 == 0) _m >>= 1, t ++;
        m = _m, n = max (_n - t, 0);
        return (solve () + 1ll * min (_n, t) * f[n][0]) % mod;
    }
};

TCO 2013 Finals TBlocks

似乎没有想象中恶心……
分类讨论距离不大于2的格子，可以发现，相邻的情况和在斜的情况都很简单，只有相距两格有问题。
按照相邻两格建图，对于一个点数为 $N$ 的连通块，考虑贡献：
只有一个环：1
只有一个相邻情况：1
只有一个斜情况：2
无环无相邻情况无斜情况：3N+1
其他：0

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <vector>
# include <string>
# include <iostream>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
using namespace std;
# define v g[i].y
# define P 1000000007
int dx0[] = {-1, 0, 1, 0};
int dy0[] = {0, -1, 0, 1};
int dx1[] = {-1, -1,  1,  1};
int dy1[] = {-1,  1, -1,  1};
# define NR 60
# define PR 2600
struct Edge {int y, frt; void Set (int yr, int fr) {y = yr, frt = fr;}} g[PR * 50];
class TBlocks
{
private:
    bool mp[NR][NR], vis[PR];
    int z[PR], pos[PR], gsz, n, m, __poc;
    void AE (int x, int y) {g[++ gsz].Set (y, pos[x]), pos[x] = gsz;}
    inline bool vaild (int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m;}
    inline int poi (int x, int y) {return (x - 1) * m + y;}
    int dfs (int x, int pre)
    {
        __poc ++, vis[x] = true;
        int res = z[x], rc = 0;
        REP_G (i, x)
        {
            if (v == pre) continue;
            if (vis[v]) rc ++;
            else
            {
                int ty = dfs (v, x);        
                if (!ty) continue;
                else if (ty < -1) rc += -ty - 1;
                else if (res != 0) res = -1;
                else res = ty;
            }
        }
        if (rc > 2) return -1;
        if (rc > 0) return res != 0 ? -1 : -1 - rc;
        return res;
    }
    int solve ()
    {
        gsz = 0;
        REP (i, n * m) z[i] = pos[i] = 0, vis[i] = false;
        REP (i, n)
            REP (j, m)
            {
                if (!mp[i][j]) continue;
                int u = poi (i, j);     
                REP_0 (d, 4)
                    if (!vaild (i + dx0[d], j + dy0[d]) || mp[i + dx0[d]][j + dy0[d]])
                    {
                        if (z[u]) return 0;
                        z[u] = 1;
                    }
                REP_0 (d, 4) 
                    if (vaild (i + dx1[d], j + dy1[d]) && mp[i + dx1[d]][j + dy1[d]]) 
                    {
                        if (z[u]) return 0;
                        z[u] = 2;
                    }
                REP_0 (d, 4) 
                    if (vaild (i + dx0[d] * 2, j + dy0[d] * 2) && mp[i + dx0[d] * 2][j + dy0[d] * 2]) 
                        AE (u, poi (i + dx0[d] * 2, j + dy0[d] * 2));
            }
        int res = 1, cnt2 = 0;
        REP (i, n)
            REP (j, m)
            {
                if (!mp[i][j] || vis[poi (i, j)]) continue;
                __poc = 0; int ty = dfs (poi (i, j), 0);
                if (ty == -1) return 0;
                if (ty == -2 || ty == -3) {res <<= 1; if (res >= P) res -= P;}
                if (ty == 2) cnt2 ++;
                if (!ty) res = 1ll * res * (3 * __poc + 1) % P;
            }
        REP (i, cnt2 / 2) {res <<= 1; if (res >= P) res -= P;}
        return res;
    }
public:
    int count (vector <string> board)
    {
        n = board.size (), m = board[0].size ();
        int cnt = 0, px[20], py[20];
        REP_0 (i, n) 
            REP_0 (j, m)
            {
                if (board[i][j] == '*') px[cnt] = i + 1, py[cnt] = j + 1, cnt ++;
                else mp[i + 1][j + 1] = board[i][j] == 'o';
            }
        int M = 1 << cnt, res = 0;
        REP_0 (s, M)
        {
            REP_0 (i, cnt) if (s >> i & 1) mp[px[i]][py[i]] = true;
            res += solve (); if (res >= P) res -= P;
            REP_0 (i, cnt) if (s >> i & 1) mp[px[i]][py[i]] = false;
        }
        return res;
    }
};