ZJUT12 Day2

1、CF 963A Alternating Sum

tags：數學

一開始觀察式子想到左右同乘 $(a - b)$ 。因為 $(a-b)\Sigma_{i=0}^na^{n-i}b^i=a^{n+1}-b^{n+1}$ 。

然後發現化簡出來的結果是 $s_0a^{n+1}-s_nb^{n+1}+\Sigma_{i=0}^{n-1}(s_{i+1}-s_i)a^{n-i}b^{i+1}$ ，前面很好算，後面一部分還是裂了。如果能降低大部分運算規模比如 $n$ 變成 $n\over2$ 就可以分治了，可惜分不得。

實際上這玩意可以分成若干塊計算。因為 $k$ 的規模比較小，所以我們可以考慮先把前 $k$ 項的值計算出來記作 $Z$ 。那麼 $0\text{~}k-1$ 的值已經算出來了， $k\text{~}2k-1$ 的值實際上只需要把 $Z$ 乘上 $({b\over{a}})^k$ ，這個觀察式子就可以看出來。當時做題的時候沒想到。

那麼同理可以得到後面若干塊的式子，之後 $Z$ 可以全部提出來，只剩一個等比數列求和。

不過要注意的是這裡 $({b\over a})^k$ 可能會等於1，並且此時 $a$ 和 $b$ 可能不相等，因為實際上這個式子等於 $b$ 乘上 $a^{-1}$ 的 $k$ 次方。特判一下就好了。

其實這個做法不一定要求 $k$ 是 $n + 1$ 的倍數。不是倍數的時候可以先預處理出前 $k$ 個式子的值，然後在最後一塊去找到對應的值加上即可。不過稍微麻煩了一點。

複雜度 $O (k + C)$ ， $C$ 是一個稍微有點大的常數。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 9;
const int MAXK = 1e5 + 10;
char s[MAXK];
ll qpow(ll a, ll b)
{
    ll res = 1; a %= MOD;
    while (b)
    {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD; b >>= 1;
    }
    return res;
}
int main()
{
    ll n, a, b, k; cin >> n >> a >> b >> k;
    scanf("%s", s);
    ll Z = 0;
    for (int i = 0; i < k; ++i)
        Z = (Z + (s[i] == '+'? 1: -1) * qpow(a, n - i) * qpow(b, i) % MOD) % MOD;
    ll q = (qpow(b, k) * qpow(qpow(a, MOD - 2), k) % MOD + MOD) % MOD;
    if (q == 1)
        cout << ((n + 1) / k * Z % MOD + MOD) % MOD << endl;
    else
        cout << (Z * (1 - qpow(q, (n + 1) / k)) % MOD * qpow(1 - q, MOD - 2) % MOD + MOD) % MOD << endl;
    return 0;
}

2、CF 1137B Camp Schedule

tags：字串，KMP，雜湊

因為要子串出現次數最多，那麼肯定要儘量提高 $0, 1$ 出現的重複率。

如果我們已經排好了一個子串，很顯然我們不可能再在後面從頭開始排，這樣子需要的數位個數是整個子串的長度。所以嘗試把後面的子串往前縮，就發現要求最長公共前字尾長度。

正解是KMP的next[m]，求出來即可。這題不難。

複雜度 $O (n + m)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
char s[MAXN], t[MAXN];
char ans[MAXN];
int nxt[MAXN];
int cnt[2];
int main()
{
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 2, j = 0; i <= m; ++i)
    {
        while (j > 0 && t[j + 1] != t[i]) j = nxt[j];
        if (t[j + 1] == t[i]) ++j;
        nxt[i] = j;
    }
    for (int i = 1; i <= n; ++i) cnt[s[i] - '0']++;
    int pos = 1;
    for (int j = 1; ; ++pos)
    {
        if (cnt[t[j] - '0'] > 0) ans[pos] = t[j], --cnt[t[j] - '0'];
        else break;
        if (j == m) j = nxt[j] + 1;
        else ++j;
    }
    while (cnt[0]) ans[pos++] = '0', --cnt[0];
    while (cnt[1]) ans[pos++] = '1', --cnt[1];
    cout << ans + 1 << endl;
    return 0;
}

那麼為什麼我做這道水題呢？其實是想練一下雜湊，因為學完之後還沒有實際上手操作過。

結果這題TM剛好卡了自然溢位。

我就一直在那邊納悶這演演算法如此完美怎麼會WA，明明KMP都已經過了…

卡了兩個小時，換了各種各樣奇怪的質數，甚至嘗試了雙雜湊還是炸了。百思不得其解，去洛谷翻題解發現是卡了自然溢位。換了個模數一下就過了。氣死我了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 5e5 + 10, P = 13331, MOD = 1e9 + 7;
char s[MAXN], t[MAXN];
char ans[MAXN];
int cnt[2];
int main()
{
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    ll prev = 0, latt = 0, powP = 1; int maxi = 0;
    
    for (int i = 1; i <= m - 1; ++i)
    {
        prev = (prev * P % MOD + t[i] - '0') % MOD;
        latt = ((t[m - i + 1] - '0') * powP % MOD + latt) % MOD;
        powP = powP * P % MOD;
        if (prev == latt) maxi = i;
    }
 
    for (int i = 1; i <= n; ++i) cnt[s[i] - '0']++;
    int pos = 1;
    for (int j = 1; ; ++pos)
    {
        if (cnt[t[j] - '0'] > 0) ans[pos] = t[j], --cnt[t[j] - '0'];
        else break;
        if (j == m) j = maxi + 1;
        else ++j;
    }
    while (cnt[0]) ans[pos++] = '0', --cnt[0];
    while (cnt[1]) ans[pos++] = '1', --cnt[1];
    cout << ans + 1 << endl;
    return 0;
}