PartisanGame
给定 \(n\) 个石子和两个正整数集合 \(A,B\)，Alice、Bob 轮流操作，Alice 先手，每次可以取对应集合内的正整数个石子，不能操作的人输，求谁获胜。
\(n\le 10^9\)，\(A,B\subseteq\{1,2,3,4,5\}\)。
题解告诉我们直接找循环节即可。
#include<vector>
#include<string>
using namespace std;
typedef vector<int> VI;
class PartisanGame {
static const int N = 5000;
bool a[N], b[N];
int buc[1024];
public:
string getWinner(int n, VI A, VI B){
memset(buc, 0, sizeof buc);
a[0] = b[0] = 0;
for(int i = 1;i <= n;++ i){
a[i] = b[i] = 0;
for(int j : A) a[i] |= i >= j && !b[i-j];
for(int j : B) b[i] |= i >= j && !a[i-j];
if(i < 5) continue;
int msk = 0;
for(int j = 0;j < 5;++ j)
msk = msk<<2 | a[i-j]<<1 | b[i-j];
if(buc[msk]){
int len = i - buc[msk];
n = i + (n-i) % len;
} else buc[msk] = i;
}
return a[n] ? "Alice" : "Bob";
}
};
KthStringAgain
给定小写字符串 \(s\)，按如下方式给定大小为 \(2^{|s|}\) 的可重字符串集合：
start with an empty collection
for each subset X of the set {1,2,...,|s|}:
take a new string t and initialize it to the given string s
for i = 1,2,...,|s|:
if X contains i:
reverse the last i characters of t
add the string t to the collection
求字典序第 \(k\) 小的字符串。
\(|s|\le 50\)，\(1\le k\le 2^{|s|}\)。
倒着考虑这个过程，如果没有翻长为 \(|s|\) 的后缀，\(s_1\) 仍在开头，否则 \(s_1\) 在结尾，\(s[2:n]\) 翻到了前面，同样可以类似地考虑 \(s_2,s_3,\cdots\)，所以这个过程相当于维护两个 stack，按顺序 push \(s_1,s_2,\cdots,s_n\)，然后拼起来。
这就可以方便地按位贪心了，复杂度 \(O(|s|^3|\Sigma|)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
class KthStringAgain {
static const int N = 51;
int n; string S;
LL f[N][N];
LL calc(const string &T){
int m = T.size(); LL res = 0;
memset(f, 0, sizeof f); f[0][0] = 1;
for(int i = 0;i < n;++ i)
for(int j = 0;j <= i;++ j){
if(j >= m || S[i] == T[j]) f[i+1][j+1] += f[i][j];
int t = n-1-i+j;
if(t >= m || S[i] == T[t]) f[i+1][j] += f[i][j];
}
for(int i = 0;i <= n;++ i) res += f[n][i];
return res;
}
public:
string getKth(string S, LL k){
n = S.size(); this->S = S;
string res;
for(int i = 0;i < n;++ i)
for(char j = ‘a‘;j <= ‘z‘;++ j){
LL tmp = calc(res+j);
if(k > tmp) k -= tmp;
else {res += j; break;}
}
return res;
}
};
FibonacciStringSum
定义没有相邻 1 的 01 串是 Fib 串。
给定正整数 \(n\) 和自然数 \(a,b\)，定义 01 串 \(s\) 的权值是 \(x^ay^b\)，其中 \(x,y\) 分别是 \(s\) 中 \(0,1\) 的个数。
求所有长为 \(n\) 的 Fib 串的权值之和\(\bmod(10^9+7)\)。
\(n\le 10^9\)，\(a,b\le 25\)。
首先把 \(x^ay^b\) 按第二类斯特林数展开成组合数，得到一个线性递推的 dp。
直接矩阵乘法不太行，但因为这个矩阵比较稀疏，用 BM 算法求出线性递推式即可。
复杂度 \(O(K^2\log n)\)，\(K\) 是递推式阶数，不知道为什么实际上非常小，只有 \(100\) 左右。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 222, mod = 1e9+7;
void qmo(int &x){x += x >> 31 & mod;}
template<typename T>
bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
int ksm(int a, int b){
int r = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) r = (LL)r * a % mod;
return r;
}
class FibonacciStringSum {
int S[26][26], dp[N][26][26], x[N], dt[N], fa[N], cnt, f[N], bs[30][N], K;
vector<int> R[N];
void mul(int *a, int *b, int *c){
static int res[N];
memset(res, 0, sizeof res);
for(int i = 0;i < K;++ i)
for(int j = 0;j < K;++ j)
res[i+j] = (res[i+j] + (LL)a[i]*b[j]) % mod;
for(int i = (K-1<<1);i >= K;-- i){
for(int j = 0;j < K;++ j) res[i-j-1] = (res[i-j-1] + (LL)res[i]*R[cnt][j]) % mod;
res[i] = 0;
} memcpy(c, res, K<<2);
}
public:
int get(int n, int a, int b){
memset(dp, 0, sizeof dp);
memset(x, 0, sizeof x);
memset(dt, 0, sizeof dt);
memset(fa, 0, sizeof fa);
memset(f, 0, sizeof f);
memset(bs, 0, sizeof bs);
cnt = 0; S[0][0] = 1;
for(int i = 1;i < 26;++ i)
for(int j = 1;j <= i;++ j)
S[i][j] = ((LL)S[i-1][j]+S[i-1][j-1])*j % mod;
dp[0][0][0] = dp[1][0][1] = dp[1][1][0] = 1; dp[1][0][0] = 2;
x[0] = !(a||b); x[1] = !a+!b;
for(int i = 2;i < N;++ i)
for(int j = 0;j <= a;++ j)
for(int k = 0;k <= b;++ k){
qmo(dp[i][j][k] = dp[i-1][j][k] + dp[i-2][j][k] - mod);
if(j){
qmo(dp[i][j][k] += dp[i-1][j-1][k] - mod);
qmo(dp[i][j][k] += dp[i-2][j-1][k] - mod);
if(k) qmo(dp[i][j][k] += dp[i-2][j-1][k-1] - mod);
}
if(k) qmo(dp[i][j][k] += dp[i-2][j][k-1] - mod);
x[i] = (x[i] + (LL)dp[i][j][k]*S[a][j]%mod*S[b][k]) % mod;
}
for(int i = 0;i < N;++ i){
if(!cnt){
if(x[i]){
fa[0] = i; dt[i] = x[i];
R[++cnt].resize(i+1);
} continue;
}
int m = R[cnt].size();
dt[i] = x[i]; fa[cnt] = i;
for(int j = 0;j < m;++ j)
qmo(dt[i] -= (LL)x[i-j-1]*R[cnt][j]%mod);
if(!dt[i]) continue;
int id = cnt-1, len = i-fa[id]+R[id].size();
for(int j = 0;j < cnt-1;++ j)
if(chmin(len, i-fa[j]+(int)R[j].size())) id = j;
int tmp = (LL)dt[i]*ksm(dt[fa[id]],mod-2) % mod;
R[cnt+1] = R[cnt];
if(R[cnt+1].size() < len) R[cnt+1].resize(len);
qmo(R[cnt+1][i-fa[id]-1] += tmp - mod);
for(int j = 0;j < R[id].size();++ j)
qmo(R[cnt+1][i-fa[id]+j] -= (LL)tmp*R[id][j]%mod);
++cnt;
}
K = R[cnt].size();
bs[0][1] = f[0] = 1;
for(int i = 0;i < 29;++ i) mul(bs[i], bs[i], bs[i+1]);
for(int i = 29;~i;-- i) if(n>>i&1) mul(f, bs[i], f);
int ans = 0;
for(int i = 0;i < K;++ i) ans = (ans + (LL)f[i]*x[i]) % mod;
return ans;
}
};