ZJUT12 Day2

1、CF 963A Alternating Sum

tags：數學

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

然后發現化簡出來的結果是 s 0 a n + 1 ? s n b n + 1 + Σ i = 0 n ? 1 ( s i + 1 ? s i ) a n ? i b i + 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} s0?an+1?sn?bn+1+Σi=0n?1?(si+1??si?)an?ibi+1，前面很好算，后面一部分還是裂了，如果能降低大部分運算規模比如 n n n變成 n 2 n\over2 2n?就可以分治了，可惜分不得，

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

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

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

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

復雜度 O ( k + C ) O(k+C) O(k+C)， C 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 0,1 0,1出現的重復率，

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

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

復雜度 O ( n + m ) O(n+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;
}