CSP-S加赛1

A. antipalindrome

真 · 签到题

然后忘了给 \(m\) 取模， 挂了 \(10pts\)

考虑任何大于\(1\) 的回文， 必然存在相邻两个字母相同，或者中间隔一个字母，那么从前往后考虑每一个位置，他有 \(m - 2\) 种可选方案

答案就是 \(m * (m - 1) * (m - 2) ^{n - 2}\)

#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qpow(ll x, ll y){
	ll ans = 1;
	for(; y; y >>= 1, x = x * x % mod)if(y & 1)ans = ans * x % mod;
	return ans;
}
ll n, m;
ll work(){
	m %= mod;
	if(n == 1)return m;
	if(n == 2)return m * (m - 1) % mod;
	if(m == 1)return 0;
	return m * (m - 1) % mod * qpow(m - 2, n - 2) % mod;
}
int main(){
	int t; scanf("%d",&t);
	for(int ask = 1; ask <= t; ++ask){
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",work() % mod);
	}
	return 0;
}

B. ZZH与计数

预处理打挂了， 然后没捞到暴力分...

发现对于一个数 \(i\)， 它有 \(a\) 位为 \(1\)， \(b\) 位为 \(0\)， 那么对于 \(a\) 中 \(x\) 位为 \(1\)， \(b\) 中 \(y\) 位为 \(1\) 的所有数，得到他们的概率是一样的， 可以用数学归纳法证明

进一步扩展，发现对 \(a\) 相同的 \(i\) 到相同的 \(x\)， \(y\), 概率也是一样的

所以我们可以按照 \(a\) 进行处理，得到 \(f_{a, x ,y}\)

然后进行一些 \(dp\) 得到答案

先考虑如何求得 \(f\)

发现当 \(a, b\) 确定时， 从二元组 \((i, j)\) 转移到 \((x, y)\) 的概率是不变的， 于是我们可以用矩阵乘法进行转移，快速幂优化一下

转移矩阵系数，在 \(i >= x j >= y\) 时， 有 \(p\) 概率操作， 一共\(2^{i + j}\)种结果， 其中 \(C_i^xC_j^y\)种为目标状态，于是这部分系数为 \(p * C_i^xC_j^y * inv(2^{i+ j})\)

类似的可以得到 \(i <= x j <= y\) 的转移系数，这里不再展开

最后从矩阵转存到\(f\)数组对应位时乘上\(inv(C_a^xC_b^y)\)

对于这部分矩阵乘法，有 \(n^2\)个二元组，这是 \(n^4\)的矩阵， 每次乘法都是 \(n^6\), 所以一共复杂度 \(n^7log m\)

好像有亿点大， 所以优化一下常数， 发现每次使用的数满足 \(x <= a\), \(y <= b\)，每次只对他们进行标号，不必每次跑 \(n^4\)矩阵， 这样我们给它乘上了一个非常小的常数 (\(< 1\)) 所以复杂度就正确了

再考虑 \(dp\)，设\(dp_{i, s, a, b}\) 表示处理完了前 \(i - 1\) 位， 答案的前 \(i - 1\) 位为 \(s\) 的前 \(i - 1\) 位， \(s\) 的剩余位是未处理的原始值, 还需要\(a\) 位原始值为 \(1\) 的位填 \(1\)， \(b\)位原始值为 \(0\) 的填 \(1\)的期望

初始状态枚举所有数 \(s\) 以及对应的 \(a, b\)

\(dp_{0, s, a, b} = v_s * f_{ct[s], a, b}\)

转移显然

答案就是 \(dp_{n, 0, 0, 0}…… dp_{n, 2^{n} - 1, 0, 0}\)