mxh带窝打多校之Contest 6

OI mxh带窝飞

---

约定

对于两个字符串$a,b$，$ab$表示$a$与$b$首尾相接得到的串。
对于两个字符串$s, S$，$s\in S$表示$s$是$S$的子串。

题意

窝严重怀疑ZJU的审美呀………………
出题人还不标数据组数呀w
感觉做起来并不是很开心呢。

1002 Bipartite Graph

给定一个无向图$G=\{V,E\}$，对于$1\leq i\leq |V|$，删除$i$号点后的图是否是二分图。

1006 First One

给出非负数列$A$，定义$\lg0=0$，求

$$\sum_{i=1}^N\sum_{j=i}^N(i+j)\lfloor\lg\sum_{k=i}^jA_k +1\rfloor$$

1010 Just A String

定义可以通过重新排列字符变成回文串的字符串为好串。
求字符集为$M$长度为$N$的随机串的期望好子串个数。

题解

1002 Bipartite Graph

由于点的问题不容易解决，考虑将问题转化到边上。
维护一个无向图$G=\{V,E\}$，支持：
1. 向图中插入边$(x,y)$。
2. 询问当前图是否是二分图。
然后就变成原题了。
用分治+并查集即可。

1006 First One

由于$A$是非负数列所以固定$i$时，$\sum_{k=i}^jA_k$是单调的。
对数的取值只有$O(\lg W)$种，因此对于每种取值维护当$i$一定时取该值的$j$的区间即可。
时间复杂度$O(N\lg W)$。

1010 Just A String

先介绍低端的做法。
考虑$F(i,j)$为长度为$i$出现次数为奇数的字符有$j$种的方案数，显然有
$F(i,j)=(j+1)F(i-1,j+1)+(M-j+1)F(i-1,j-1)$
然后枚举每种长度的子串统计贡献即可。
时间复杂度$O(N\min (N, M))$。
卡常数呀w

# include <cstdio>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
const int NR = 2020;
const int P = 1000000007;
int f[NR][NR], inv[NR];
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;}
int pw[2010][2010];
int main ()
{
    f[0][0] = 1;
    REP (i, 2000) 
    {
        pw[i][0] = 1;
        REP (j, 2000) pw[i][j] = 1ll * pw[i][j - 1] * i % P;
    }
    int n, m, q0;
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%d%d", &n, &m);
        int ans = 0;
        REP (i, n)
        {
            int len = min (m, i);
            f[i][0] = f[i - 1][1];
            f[i][len + 1] = f[i][len + 2] = f[i][len + 3] = 0;
            REP (j, len) f[i][j] = (1ll * (j + 1) * f[i - 1][j + 1] + 1ll * (m - j + 1) * f[i - 1][j - 1]) % P;
        }
        REP (i, n) ans = (ans + 1ll * (n - i + 1) * pw[m][n - i] % P * (f[i][0] + f[i][1])) % P;
        printf ("%d\n", ans);
    }
    return 0;
}

高端做法写完再说好啦。