因为题面记不清楚了，所以比较简略。

game

题意

Texas 和 Exusiai 两个人在玩一个游戏，Texas 能挑战 A(A\leq 10^6) 次 ，Exusiai 能挑战 B(B\leq 10^9) 次，每人每次挑战有 p_i 的概率成功并获得 1 点积分。求两人用光所有挑战次数后 Exusiai 的积分严格大于 Texas 的概率。

思路

每人每次挑战是不互相影响的，它符合伯努利实验二项分布。套公式，对于每个 i\leq A 分别求出每个人的积分恰好为 i 的概率。最后枚举 i ，统计 Exusiai 的积分为 i 且 Texas 的积分小于 i 的概率，再加上 Exusiai 的积分大于 A 的概率即可。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=5500000;
const int MOD=10000019;
int a[MAXN], b[MAXN];
int inv[MAXN];
int facv[MAXN], facn[MAXN];
int powp[MAXN], powq[MAXN];
int read()
{
    int x=0; char ch=0;
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return x;
}
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%MOD;
        n=1ll*n*n%MOD; k>>=1;
    }
    return r;
}
void calc(ll n, int p, int k, int* a)
{
    facv[0]=facn[0]=powp[0]=1;
    powq[k]=qpow(1-p+MOD, (n-k+MOD-1)%(MOD-1));
    for (int i=1; i<=k; i++)
    {
        facv[i]=1ll*facv[i-1]*inv[i]%MOD;
        facn[i]=(n-i+1+MOD)%MOD*facn[i-1]%MOD;
        powp[i]=1ll*powp[i-1]*p%MOD;
    }
    for (int i=k-1; i>=0; i--) powq[i]=1ll*(1-p+MOD)*powq[i+1]%MOD;
    for (int i=0; i<=k; i++)
        a[i]=1ll*facn[i]*facv[i]%MOD*powp[i]%MOD*powq[i]%MOD;
}
int main()
{
//  freopen("game.in", "r", stdin);
//  freopen("game.out", "w", stdout);
    int n, A, p=0; ll B;
    scanf("%d%d%lld", &n, &A, &B);
    for (int i=1; i<=n; i++) p=(p+read())%MOD;
    p=1ll*p*qpow(n, MOD-2)%MOD;
    inv[1]=1;
    for (int i=2; i<=A; i++)
        inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
    calc(A, p, A, a); calc(B, p, min(1ll*A, B), b);
    int sum=0, rst=1, ans=0;
    for (int i=0; i<=A; i++)
    {
        ans=(ans+1ll*sum*b[i])%MOD;
        sum=(sum+a[i])%MOD; rst=(rst-b[i]+MOD)%MOD;
    }
    ans=(ans+1ll*sum*rst)%MOD;
    printf("%d\n", ans);
    return 0;
}

rotate

题意

给出一个 n\times m 的网格，其中一些格子里有金币。你操控一个机器人从某一个格子开始沿某一方向行进，若碰到一枚金币会拾取这枚金币并改变方向（只能左转或右转）。求是否能取走所有金币。

思路

把行和列看成点，建二分图，有金币的格子的行和列之间连边。题目转化为一笔画问题，即只经过每条边一次并遍历所有边是否可行。DFS/并查集判断若只有一个大于 1 的连通块且度为奇数的点数小于等于 2 则可行，否则不可行。

代码

#include <cstdio>
const int MAXN=110;
const int MAXM=220;
char a[MAXN][MAXN];
int d[MAXM], f[MAXM], s[MAXM];
int getf(int x)
{
    if (x==f[x]) return x;
    return f[x]=getf(f[x]);
}
int main()
{
//  freopen("rotate.in", "r", stdin);
//  freopen("rotate.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i=1; i<=n; i++) scanf("%s", a[i]+1);
        for (int i=1; i<=n+m; i++) d[i]=0, f[i]=i, s[i]=1;
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
                if (a[i][j]=='o')
                {
                    int x=getf(i), y=getf(j+n);
                    if (x!=y) f[x]=y, s[y]+=s[x], s[x]=0;
                    d[i]++; d[j+n]++;
                }
        int blk=0;
        for (int i=1; i<=n+m; i++)
            if (f[i]==i&&s[i]>1) blk++;
        int cnt=0;
        for (int i=1; i<=n+m; i++)
            if (d[i]&1) cnt++;
        puts(blk<=1&&cnt<=2?"Possible":"Impossible");
    }
    return 0;
}

password

题意

给定两个字符串s、t，求s的非空前缀后接上t的非空前缀形成的本质不同字符串种类数。

思路

设一组本质相同的答案串为 AB ，且 A, B 分别为 s, t 的非空前缀。我们在这堆本质相同的串里，选出 A 最短、B 最长的一种（记为 A'B' ）代表这一类。那么答案就是所有串的个数减去重复的。设 A''B'' 与 A'B' 重复，那它应该是长这样的： 上图颜色相同的线段代表字串相同。 容易看出 B'' 是 B' 的 Border（既是前缀又是后缀），并且 B' 去掉 B'' 这一段在 A 中出现过（绿色的两段）。可以 kmp/exkmp 求出 t 的前缀的 Border 和 t 的每个前缀在 s 中出现的次数。 但是还有个问题。如果我们枚举 t 的每个前缀，再枚举它的每一个 Border，该怎么确定它是 A 最短、B 最长的呢？ 我们考虑对于 t 的每一个前缀，只减去它的最长 Border 的贡献。这样，如果有更长的 B 仍能与另一个 A 构成这个串，这个新 B 就会减去原来的贡献。而最长的前缀 B' 的贡献是唯一的不会被减去的那个。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=220000;
char s[MAXN], t[MAXN];
int f[MAXN], g[MAXN], cnt[MAXN];
void kmp(char* s, int n)
{
    for (int i=2; i<=n; i++)
    {
        f[i]=f[i-1];
        while (f[i]&&s[f[i]+1]!=s[i]) f[i]=f[f[i]];
        f[i]=(s[f[i]+1]==s[i]?f[i]+1:f[i]);
    }
}
void exkmp(char* s, int n)
{
    for (int i=2, p=1; i<=n; i++)
    {
        g[i]=max(0, min(g[i-p+1], p+g[p]-i));
        while (i+g[i]<=n&&s[i+g[i]]==s[1+g[i]]) g[i]++;
        if (i+g[i]>p+g[p]) p=i;
    }
    g[1]=n;
}
int main()
{
//  freopen("password.in", "r", stdin);
//  freopen("password.out", "w", stdout);
    scanf("%s%s", t+1, s+1);
    int n=strlen(s+1);
    kmp(s, n);
    int ls=n, lt=strlen(t+1);
    s[++n]='#';
    for (int i=1; i<=lt; i++) s[++n]=t[i];
    exkmp(s, n);
    for (int i=ls+3; i<=n; i++) cnt[g[i]]++;
    for (int i=ls; i>=1; i--) cnt[i]+=cnt[i+1];
    ll ans=1ll*lt*ls;
    for (int i=1; i<=ls; i++)
        if (f[i]) ans-=cnt[i-f[i]];
    printf("%lld\n", ans);
    return 0;
}