前言:
应该没什么人打这场吧。。
写个题解给自己看了。
K 不会,其他的都不是很难,顶多G和H算midium难度。
A用python写实在是太好写了!!!我用C++写了一大坨样例过不去,用python三两下就整完了,感受到了python做模拟题的方便。
H.原始串的个数
题意:求长度为n的非周期二进制字符串的数量。即没有长度 < n的循环节。
做法一(dp):
考虑f[i]为长度为i的非周期二进制字符串的数量,显然01能够构成的字符串数量是2^i个,对于不合法的数量,那就是这个串有循环节,即循环节的长度是i的因子。
那么dp的转移方程就是,f[i] = qpow(2, i) - f[d] ,其中d是i的因子。
int f[N];
void solve()
{
int n;
cin >> n;
f[0] = 1;
int mul = 1;
for (int i = 1; i <= n; i++)
{
f[i] += mul * 2 % mod;
for (int j = i * 2; j <= n; j += i)
{
f[j] -= f[i];
f[j] %= mod;
}
mul = mul * 2 % mod;
}
for (int i = 1; i <= n; i++)
{
cout << (f[i] + mod) % mod << "\n";
}
}
做法二:(偷鸡)
打开OEIS输入给的样例,就会发现一个公式:
于是套个莫比乌斯反演的板子就能水过去了。。
int f[N], g[N];
int mu[N], flg[N], p[N];
void getMu(int n)
{
int tot = 0;
mu[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!flg[i]) p[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= n; ++j)
{
flg[i * p[j]] = 1;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
}
void solve()
{
int n;
cin >> n;
getMu(n);
g[0] = 1;
for (int i = 1; i <= n; i++) g[i] = g[i - 1] * 2 % mod;
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j += i)
{
f[j] += g[j / i] * mu[i];
f[j] %= mod;
}
}
for (int i = 1; i <= n; i++) cout << (f[i] + mod) % mod << "\n";
}
G.猫雷的复活赛
题意:两个人博弈,从(0,0)位置开始移动,每次可以移动【1,k】之间的一个整数,终点是(n,m),谁先无法操作谁就输了,问谁能赢。
做法:
先简单证明下一维的情况:
从终点往前考虑,就能看出来哪些是必胜区间,哪些是必败区间了。
于是就可以得到结论:n % (k + 1) != 0时,那就必胜。
对于二维的情况,可以把他们当成两个独立的游戏,在博弈论中,两个互相独立的游戏,他们的结果异或起来,为0那就是输,不为0那就是赢。具体证明可以见进阶指南p187和p188的例题。
于是这题就做完了。