牛客训练赛6补题记录

H: Harmony Pairs 数位dp

万恶的数位dp

在dp时，其实我们并不关心$A,B$分别是多少，只关心$S(B)-S(A)$等于多少，该状态占一维。

还要考虑$B\le N$，$A=B$两类限制，因此再多出两维。

AC代码：（delta代表$S(B)-S(A)$的值）

2020-11-8：把这题又做了一遍，这次的代码比较好看，于是把旧的删掉了

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll mod = 1e9 + 7;
char digit[120];
ll dp[121][2001][2][2];
int len;

ll calc(int l, int diff, bool lim, bool greater){
    if(l == len) {
        return diff > 1000;
    }

    ll & ans = dp[l][diff][lim][greater];
    if(ans != -1) return ans;

    ans = 0;
    int mxB = lim?digit[l]:9;
    for(int dB = 0; dB <= mxB; dB++){
        for(int dA = 0; dA <= (greater?9:dB); dA++){
            ans += calc(l + 1, dA - dB + diff, lim && (dB == mxB), greater || (dB > dA));
        }
    }
    ans %= mod;
    return ans;
}

void solve(){
    memset(dp, -1, sizeof dp);
    cin >> digit;
    len = strlen(digit);
    for(int i=0; i<len; i++) digit[i] -= '0';
    cout << calc(0, 1000, true, false);
}

signed main(){
    Android;
    solve();
}

B: Binary Vector 公式递推

对于$N$维向量组，考虑每次随机向其中加入一个向量（直至向量组的秩$R=N$）。

显然，若当前向量组的大小为$x$，那么加入一个新向量$v$有$2^N$种可能，其中会导致向量组线性相关的有$2^x$种可能。（即：从原向量组$x$个向量中任选几个相异或，有$2^x$种可能的结果）。

因此，该题的公式为

$$f_n=\prod_{i=0}^{n-1} \frac{2^n-2^i}{2^n}=\frac{\prod\limits_{i=0}^{n-1}(2^n-2^i)}{2^{n^2}}$$

“容易”发现

$$f_n=\frac{2^{n-1}f_{n-1}*(2^n-1)}{2^{2n - 1}}$$

线性递推即可。

AC代码：

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

template<typename F, typename... Args>
void timeit(F func, Args&&... args){
    clock_t start = clock();
    func(std::forward<Args>(args)...);
    # ifndef ONLINE_JUDGE
    cerr << "time: " << ((double)clock() - start) / CLOCKS_PER_SEC << endl;
    # endif
}

const int maxn = 2e7 + 1000;
const ll mod = 1e9 + 7;
const ll inv2 = 500000004;
ll ans[maxn];

ll qpow(ll base, ll t){
    ll ret = 1;
    while(t){
        if(t & 1) ret = ret * base % mod;
        t >>= 1;
        base = base * base % mod;
    }
    return ret;
}

void init(){
    ans[1] = 1 * inv2;
    ll pow2 = 2, dem = inv2;
    for(int i=2; i<maxn; i++){
        pow2 = pow2 * 2 % mod;
        dem = dem * inv2 % mod;
        ans[i] = ans[i-1] % mod * (pow2 - 1 + mod) % mod;
        ans[i] = ans[i] * dem % mod;
    }
    for(int i=2; i<maxn; i++) ans[i] = ans[i - 1] ^ ans[i];
}

void solve(){
    int n; cin >> n;
    cout << ans[n] << '\n';
}

signed main(){
    timeit(init);
    Android;
    int t; cin >> t;
    while(t--)
        solve();
}

G: Grid Coloring 构造

有一种很巧妙的方法

AC代码:

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 4e4 + 1000;

int n, k;
int hor[maxn], ver[maxn];

void solve(){
    cin >> n >> k;
    if(n == 1 || 2 * n * (n + 1) % k != 0 || k == 1){
        cout << "-1\n";
        return;
    }
    if(n % k != 0){
        int color = 1;
        for(int r = 0; r < 2 * (n + 1); r++){
            for(int c = 0; c < n; c++){
                cout << color << " ";
                color = color % k + 1;
            }
            cout << '\n';
        }
    }else{
        int color = 0;
        for(int r = 0; r < 2 * (n + 1); r++){
            int init = (r & 1) + 1;
            for(int c = 0; c < n; c++){
                cout << init << " ";
                init = init % k + 1;
            }
        }
        cout << '\n';
    }
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--)
        solve();
}

J: Josephus Transform 结合律

对于一个置换操作，可以视作矩阵乘法，如下所示。

$$\begin{aligned}\begin{bmatrix} 0/1& 0/1& 0/1\\ 0/1& 0/1& 0/1\\ 0/1& 0/1& 0/1\\\end{bmatrix} \begin{bmatrix} a\\ b\\ c\end{bmatrix}=\begin{bmatrix} a'\\ b'\\ c'\end{bmatrix}\end{aligned}$$

考虑到矩阵乘法具有结合律，因此推测置换操作也具有结合律！因此可以使用快速幂。具体细节或证明见置换群笔记（或许会有？）。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r == 0 ? ' ' : '\n')
#define pii pair<int, int>
#define sqr(x) ((x) * (x))
using namespace std;

const int maxn = 1e5 + 1000;
int sum[maxn], ans[maxn], tmp[maxn], tmp_a[maxn];

void change(int pos, int n, int delta){
    for(; pos <= n; pos += pos & (-pos)) sum[pos] += delta;
}

int query(int k, int n){
    int pos = 0, cnt = 0;
    for(int i=20; i>=0; i--){
        pos += 1 << i;
        if(pos > n || cnt + sum[pos] >= k){
            pos -= 1 << i;
        }else{
            cnt += sum[pos];
        }
    }
    return pos + 1;
}

void apply(int * dest, int * rule, int n){
    for(int i=1; i<=n; i++){
        tmp_a[i] = dest[rule[i]];
    }
    memcpy(dest, tmp_a, (n + 1) * sizeof(int));
}

void solve() {
    int n, m, k, x;
    cin >> n >> m;

    for(int i=1; i<=n; i++) ans[i] = i;

    while(m--){
        for(int i=1; i<=n; i++) change(i, n, 1);

        cin >> k >> x;
        int cur = k - 1, v;
        for(int i=1, remain = n; i<=n; i++, remain--){
            v = query(cur + 1, n);
            tmp[i] = v;
            change(v, n, -1);
            if(remain != 1) cur = (cur + k - 1) % (remain - 1);
        }
        
        while(x){
            if(x & 1) apply(ans, tmp, n);
            x >>= 1;
            apply(tmp, tmp, n);
        }
    }

    for(int i=1; i<=n; i++){
        cout << ans[i] << (i == n?'\n':' ');
    }
}

signed main() {
    Android;
    solve();
}

E: Easy Construction 构造

给定 n,k，问是否可以构造一个 1~n 的排列 P，使得对于 1~n 中任意的数 i，P 都存在一个 长为 i 的子区间，其和模 n 余 k。有解输出任意一组，无解输出 -1。

策略如下：

假设有解，则存在长度为$n$子序列满足条件，因此有$\frac{n(n+1)}{2}\equiv k \mod n$

• 若$n$为偶数，因为$\frac{n}{2}n + \frac{n}{2}\equiv k \mod n$，所以$k=\frac{n}{2}$，构造序列$<{n, \frac{n}{2},1,n-1,2,n-2,\cdots}>$即可
• 若$n$为奇数，显然$k=0$，构造$<n,1,n-1,2,n-2,\cdots>$即可。