闲话
引流昨日闲话
以及有读者能给我讲讲最后的式子是咋化出来的吗？
模拟赛
51nod 什么寄比赛（
T1 回文划分
猜个结论，直接线性地前后每次删掉最短的 border 即可。感性理解（
然后哈希一下，维护前后 \(k\) 个的哈希即可。我们每次循环只需要 \(O(1)\) 次更新哈希值，因此总时间复杂度 \(O(Tn)\)。
每次删掉 border 对答案贡献是 2，最后如果剩一段还要加进去。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
// int mod;
// const int mod = 10007;
// const int mod = 469762049, g = 3;
// const int mod = 998244353; // const int g = 3;
// const int mod = 1004535809, g = 3;
// const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template<typename T1,typename T2>T1 add(T1 a,T2 b){return(a+=b)>=mod?a-mod:a;}template<typename T1,typename...Args>T1 add(T1 a,Args...b){return add(a,add(b...));}template<typename T1,typename T2>T1 sub(T1 a,T2 b){return(a-=b)<0?a+mod:a;}template<typename T1,typename...Args>T1 sub(T1 a,Args...b){return sub(a,add(b...));}template<typename T1,typename T2>void addi(T1&a,T2 b){(a+=b)>=mod?(a-=mod):true;}template<typename T1,typename...Args>void addi(T1&a,Args...b){addi(a,add(b...));}template<typename T1,typename T2>void subi(T1&a,T2 b){(a-=b)<0?(a+=mod):true;}template<typename T1,typename...Args>void subi(T1&a,Args...b){subi(a,add(b...));}
/* Fastmod / mul */ struct FastMod{int m;ll b;void init(int _m){m=_m;if(m==0)m=1;b=((lll)1<<64)/m;}FastMod(int _m){init(_m);}int operator()(ll a){ll q=((lll)a*b)>>64;a-=q*m;if(a>=m)a-=m;return a;}}Mod(mod);int mul(int a,int b){return Mod(1ll*a*b);}template<typename T1,typename T2>int mul(T1 a,T2 b){return Mod((long long)(1ll*a*b));}template<typename T,typename...Args>int mul(T a,Args...b){return mul(a,mul(b...));}template<typename T1,typename T2>void muli(T1&a,T2 b){a=Mod(1ll*a*b);}template<typename T1,typename...Args>void muli(T1&a,Args...b){muli(a,mul(b...));} // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp fac C */ template<typename T1,typename T2>T1 qp(T1 a,T2 b){T1 ret=1;for(;b>0;a=1ll*a*a%mod,b>>=1)if(b&1)ret=mul(ret,a);return ret;}vi __fac({1,1}),__ifc({1,1}),__inv({0,1});inline void ___prep(int n){static int i=2;if(i<n)for(__fac.resize(n),__ifc.resize(n),__inv.resize(n);i<n;i++)__fac[i]=mul(i,__fac[i-1]),__inv[i]=mul((mod-mod/i),__inv[mod%i]),__ifc[i]=mul(__inv[i],__ifc[i-1]);}inline int fac(int x){return ___prep(x+1),__fac[x];}inline int ifc(int x){return ___prep(x+1),__ifc[x];}inline int inv(int x){return ___prep(x+1),__inv[x];}inline int C(int n,int m){if(n<m or n<0 or m<0)return 0;return mul(fac(n),ifc(m),ifc(n-m));}
/* sum of i^k */ int S(int n,int k){vector<int>__pre(k+4),__suf(k+4),__pw(k+4),__pri(k+4);vector<bool>__vis(k+4,0);__pw[1]=1;for(int i=2,cnt=0;i<=k+2;++i){if(!__vis[i])__pri[++cnt]=i,__pw[i]=qp(i,k);for(int j=1;j<=cnt and i*__pri[j]<=k+2;++j){__vis[i*__pri[j]]=1;__pw[i*__pri[j]]=mul(__pw[i],__pw[__pri[j]]);if(i%__pri[j]==0)break;}}rep(i,2,k+2)__pw[i]=add(__pw[i],__pw[i-1]);__pre[0]=__suf[k+3]=1;rep(i,1,k+2)__pre[i]=mul(__pre[i-1],(n-i+mod));pre(i,k+2,1)__suf[i]=mul(__suf[i+1],(n-i+mod));int tmp=0,ret=0;rep(i,1,k+2){if((k-i)&1)subi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));else addi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));}return ret;}
// /* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1);
int n, ans, len, pw[N];
char a[N];
signed main() {
pw[0] = 1; rep(i,1,1e6) pw[i] = mul(pw[i - 1], bse);
multi {
cin >> a + 1; n = strlen(a + 1);
ans = len = 0;
for (int i = 1, hsh1 = 0, hsh2 = 0; i <= (n >> 1); ++ i) {
hsh1 = add(mul(hsh1, bse), a[i]);
hsh2 = add(hsh2, mul(pw[len], a[n - i + 1]));
++ len;
if (hsh1 == hsh2)
hsh1 = hsh2 = 0, ans += 2, len = 0;
} if ((n & 1) or len != 0) ++ ans;
cout << ans << '\n';
}
}
T2 吉利售价
我们需要的就是找到最大的 \(k\) 满足
\[x\times 10^k + \overline{ddd\dots ddd} = n\times b
\]
\]
其中 \(x, n\) 为任意非负实数，\(\overline{ddd\dots ddd}\) 表示 \(k\) 位、每位都是 \(d\) 的数字。
注意到我们没必要确定 \(x, n\)，我们只需要判断 \(k\) 是否合法即可。设 \(k = 10^k, c = \overline{ddd\dots ddd}\)，我们将两边对 \(b\) 取模，得到
\[kx + c \equiv 0 \pmod b
\]
\]
我们需要的就是找到一个合法的 \(x\) 使得上式成立。找到上式的最小非负整数解可以由拓展欧几里得算法得到。得到 \(x\) 后只需要判断 \(kx + c\) 与 \(a\) 的关系了。由于可能的 \(k\) 只有 \(10^4\) 个，每次能暴力匹配。
注意 \(d = 0\) 时 \(x\) 的取值范围是正整数。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int b, d, mod, l, pw[N], ans;
char a[N];
int qp(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
} return ret;
}
int exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return a;
} int _gcd = exgcd(b, a % b, x, y);
int t = x; x = y, y = t - a / b * y;
return _gcd;
}
int calc(int a, int b) {
int _gcd = __gcd(a, mod);
if (b % _gcd != 0) return -1;
int x, y, _a = a / _gcd, _b = b / _gcd, _mod = mod / _gcd;
int tmp = exgcd(_a, _mod, x, y);
x = 1ll * x * _b % _mod;
x = (x + _mod) % _mod;
if (d == 0 and x == 0) x += _mod;
return x;
}
signed main() {
cin >> b >> d >> a + 1;
mod = b, l = strlen(a + 1);
pw[0] = 1; rep(i,1,l + 1) pw[i] = 10ll * pw[i - 1] % mod;
for (int k = 1, sum = 0; k < l; ++ k) {
sum = (10ll * sum + d) % mod;
int x = calc(pw[k], mod - sum);
if (x == -1) continue;
int comp;
if (l - k >= 8) comp = -1;
else {
int hbit = 0;
rep(i,1,l-k) hbit = 10ll * hbit + a[i] - '0';
if (x < hbit) comp = -1;
else if (x == hbit) comp = 0;
else comp = 1;
}
if (comp == 1) continue;
else if (comp == -1) ans = k;
else {
bool flg = 1;
rep(i,l-k+1,l) if (a[i] - '0' != d) {
if (a[i] - '0' < d) flg = 0;
break;
} if (flg) ans = k;
}
}
if (d != 0) {
int sum = 0;
rep(i,1,l) sum = (10ll * sum + d) % mod;
if (sum == 0) {
bool flg = 1;
rep(i,1,l) if (a[i] - '0' != d) {
if (a[i] - '0' < d) flg = 0;
break;
} if (flg) ans = l;
}
}
cout << ans << '\n';
}
T3 首尾匹配
我为啥能想到子树线段树合并想不到转化成二维数点呢？考场上想到对称压缩后缀自动机后就回不去简单思路了（
考场降智实锤了（
我们对正反串分别建 Trie 树，然后一个串就对应一个节点，它是它子树内节点对应串的前缀/后缀。处理出 dfn 序后这个信息就连续了。
我们需要的是 \(P, Q\) 串分别在正反 Trie 上节点的子树节点集合的交，这个可以二维数点搞定。
总时间复杂度 \(O(n\log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 4e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, ans[N];
int dfn[N], ed[N];
string a[N], s1, s2;
vector<pair<string, int> > qry[N];
int id(char ch) {
if (ch == 'A') return 0;
if (ch == 'G') return 1;
if (ch == 'U') return 2;
if (ch == 'C') return 3;
assert(0);
}
int trie[N][4], cnt[N], mlc;
void insert(string s, int idk) {
int p = 0;
for (auto c : s) {
if (!trie[p][id(c)]) trie[p][id(c)] = ++mlc, dfn[mlc] = ed[mlc] = idk;
dfn[trie[p][id(c)]] = min(dfn[trie[p][id(c)]], idk), ed[trie[p][id(c)]] = max(ed[trie[p][id(c)]], idk);
p = trie[p][id(c)];
}
}
void update(string s) {
int p = 0;
for (auto c : s) {
if (!trie[p][id(c)]) trie[p][id(c)] = ++mlc;
cnt[trie[p][id(c)]]++, p = trie[p][id(c)];
}
}
int query(string s) {
int p = 0;
for (auto c : s) {
if (!trie[p][id(c)]) return -1;
p = trie[p][id(c)];
} return p;
}
signed main() {
cin >> n >> m;
rep(i,1,n) cin >> a[i];
sort(a + 1, a + n + 1);
rep(i,1,n) insert(a[i], i);
rep(i,1,m) {
cin >> s1 >> s2;
int u = query(s1);
if (u == -1) continue;
reverse(s2.begin(), s2.end());
qry[dfn[u] - 1].push_back({s2, -i});
qry[ed[u]].push_back({s2, i});
}
memset(trie, 0, sizeof trie), mlc = 0;
rep(i,1,n) {
reverse(a[i].begin(), a[i].end());
update(a[i]);
for (auto p : qry[i]) {
int id = p.second, u = query(p.first);
if (u == -1) continue;
if (id > 0) ans[id] += cnt[u];
else ans[-id] -= cnt[u];
}
}
rep(i,1,m) cout << ans[i] << "\n";
}
T4 修水管
……
有人知道我为啥沉默吧（
考虑计数一个位置 \(i\) 在 \(r\) 轮里漏水的概率是 \(P(i)\)，则答案就是
\[\sum_{i = 1}^n P(i)\times d(i)
\]
\]
我们如何计算概率呢？不难写出 \(P(1) = 1 - (1 - p(1))^r\)，但是 \(2\sim n\) 的信息需要由前面的信息得出，也就是只有前面不漏水时才可能在这里漏水。这启发我们转而 dp 求解前 \(i\) 个位置漏水次数。
不妨设 \(f(i, j)\) 表示前 \(i\) 个位置漏水次数（修补次数）为 \(j\) 次的概率。这样我们就能表示 \(P(i)\) 了。枚举 \(i\) 位置会被水经过的次数 \(j\)，以及这样的概率，再乘上 \(1\) 减去一次都不漏的概率，可以得到
\[P(i) = \sum_{j = 0}^r f(i - 1, j) \times \left(1 - (1 - p(i))^{r - j}\right)
\]
\]
\(f\) 可以由类似的方式得到。假设 \(f(i, j) = 0\) 对任意 \(j < 0\) 成立，可以得到
\[f(i, j) = f(i - 1,j - 1) \times \left(1 - (1 - p(i))^{r - j + 1}\right) + f(i - 1,j) \times (1 - p(i))^{r - j}
\]
\]
这样我们就在 \(O(Tnr)\) 的复杂度内得到了答案。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 250 + 5;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, r;
db ans, tmp, p[N], d[N], f[N][N];
db qp(db a, int b) {
db ret = 1;
while (b) {
if (b & 1) ret = a * ret;
a = a * a;
b >>= 1;
} return ret;
}
int main() {
multi {
cin >> n >> r;
rep(i,1,n) cin >> p[i] >> d[i];
rep(i,0,n) rep(j,0,r) f[i][j] = 0;
f[1][0] = qp(1 - p[1], r); f[1][1] = 1 - f[1][0];
rep(i,2,n) rep(j,0,min(i,r)) {
if (j > 0) f[i][j] += f[i - 1][j - 1] * (1 - qp(1 - p[i], r - j + 1));
if (i != j) f[i][j] += f[i - 1][j] * qp(1 - p[i], r - j);
} ans = f[1][1] * d[1];
rep(i,2,n) {
tmp = 0;
rep(j,0,min(i-1,r)) tmp += f[i - 1][j] * (1 - qp(1 - p[i], r - j));
ans += tmp * d[i];
} cout << ans << '\n';
}
}
