菜鸡和大佬队友一起报了暑假的牛客和杭电······然而自己水平完全不够做多少题就是了。
1005 博弈（hdu7437）
好吧赛时根本没写到它（)
开始看题以为得一步一步算（是什么让我有这么离谱的思路.jpg），看了官方题解才发现自己的愚蠢呜呜，就是说有没有一种可能，A和B前 \(\lfloor n/2 \rfloor\) 位的字符串情况是“等价”的？可以视为把A的字符直接换给B，两方取到每种结果的概率实际上一样。。。 但对于A而言，平局并不计入胜利情况，单独考虑平局即可。
于是开始快乐分类讨论如下:
当 \(n\) 为偶数时，设平局概率为 \(p\) ，A获胜的概率即为 \((1-p)/2\) ； \(n\) 为奇数时，由于A比B多取一个字符，若前 \((n-1)/2\) 个字符相同，则A必胜，设前 \((n-1)/2\) 个字符相同的概率为 \(p\) ，A获胜的概率为 \((1+p)/2\) .
至于如何计算平局的概率，本菜鸡的求法极其抽象（）将情况总数看作“长为 \(2n\) 的序列，每个位置在原字符集里挑选一种字符的方案数”，其中前 \((n-\lfloor n/2 \rfloor)\) 位属于A，后 \(\lfloor n/2 \rfloor\) 属于B，这样就避免了重复情况，可以用高中的排列组合知识 \(O(1)\) 计算；用 \(cnt\) 数组记录每个字母出现的次数，前 \(\lfloor n/2 \rfloor\) 个字符相同的概率可同理看作“长为 \(\lfloor n/2 \rfloor\) 的序列，在在字符集里挑选的方案数”，其中第 \(i\) 种字符只有 \(cnt[i]/2\) 个，仍然可以 \(O(1)\) 求出。此处注意 \(n\) 的奇偶情况略有不同，特判一下就好，问题不大。
主要代码如下：（好吧还是好长一坨，QwQ）
int n;
scanf("%d", &n);
int s = 0;
for(int i = 1; i <= n; i++) {
char c = getchar();
while(c < 'a' || c > 'z') c = getchar();
int h;
scanf("%d", &h);
s += h;
cnt[c - 'a'] += h;
}
if(s & 1) {
int ok = 1;
for(int i = 0; i < 26; i++) {
if(cnt[i] & 1) {
if(ok) {
ok = 0;
} else {
ok = 1;
break;
}
}
}
if(ok) {
printf("%lld\n", inv(2));
continue;
}
ll x = 1, y = 1, ys = s / 2;
for(int i = 0; i < 26; i++) {
if(!cnt[i]) continue;
x = x * c(s, cnt[i]) % mo;
s -= cnt[i];
}
for(int i = 0; i < 26; i++) {
if(cnt[i] <= 1) continue;
cnt[i] /= 2;
y = y * c(ys, cnt[i]) % mo;
ys -= cnt[i];
}
ll p = y * inv(x) % mo;
printf("%lld\n", (1 + p) * inv(2) % mo);
} else {
int ok = 0;
for(int i = 0; i < 26; i++) {
if(cnt[i] & 1) {
ok = 1;
break;
}
}
if(ok) {
printf("%lld\n", inv(2));
continue;
}
ll x = 1, y = 1, ys = s / 2;
for(int i = 0; i < 26; i++) {
if(!cnt[i]) continue;
x = x * c(ys * 2, cnt[i]) % mo;
y = y * c(ys, cnt[i] / 2) % mo;
ys -= cnt[i] / 2;
}
ll p = y * inv(x) % mo;
printf("%lld\n", (1 + mo - p) * inv(2) % mo);
}
1006 序列立方 （hdu7438）
一言以蔽之：人类智慧题（bushi
需要求出序列中每个非空子序列出现次数的立方值的和（什么绕口令），这个立方值看上去十分抽象也不好处理，于是换一种思路：在序列中可重复地取三个子序列，它们相同的情况总数。
考虑动态规划，\(dp[i][j][k]\) 表示已经选了三个相同的子序列，其结尾分别在第 \(i,j,k\) 位，故 \(a[i]=a[j]=a[k]\) 时满足条件。使用前缀和数组 \(s[i][j][k]\) 表示以 \(i,j,k\) 位结尾的方案总数，有 \(a[i]=a[j]=a[k]\) 时 \(dp[i][j][k]=s[i-1][j-1][k-1]\) ，前缀和可用容斥思想维护。
代码如下，注意代码中用ans统计答案，可略去dp数组。
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
s[i][j][0] = s[i][0][j] = s[0][i][j] = 1;
}
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= n; k++) {
ll ss = (s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1]) % mo;
ss -= (s[i - 1][j - 1][k] + s[i - 1][j][k - 1]
+ s[i][j - 1][k - 1]) % mo;
ss = (ss + mo) % mo;
ss += s[i - 1][j - 1][k - 1];
ss %= mo;
if(a[i] == a[j] && a[i] == a[k]) {
ans += s[i - 1][j - 1][k - 1];
ans %= mo;
ss += s[i - 1][j - 1][k - 1];
ss %= mo;
}
s[i][j][k] = ss;
}
}
}
printf("%lld\n", ans);