个人排位赛1补题记录

Removing Blocks(AtCoder AGC028-B)

AC代码

两种做法:

1. 考虑对于每个$a_j$，会对答案产生多少贡献。对于$i,j(i<j)$，若取走$i$时产生了$a_j$的贡献，说明$i,i+1,\dots,j$都未被取走，此时，设$len=j-i+1$$i+1,i+2,\dots,j$有$(len-1)!$中排列方法，而小于$i$或大于$j$的元素随意插入，共有$(len+1)(len+2)\dots(len-1)len$中插法。由乘法原理，可知$i$对$j$产生了$\frac{n!}{len}$次贡献

   也就是说，其他元素$i\ne j$一共会对$j$产生$cnt_j=\sum\limits_{len=2}^{j}\left(\frac{n!}{len}\right)+\sum\limits_{len=2}^{n-j+1}\left(\frac{n!}{len}\right)$次贡献，再加上$j$对自身产生的贡献次数$n!$。因此$j$一共对答案产生了$a_j(cnt_j+n!)$的贡献。

2. 考虑将代价和变成代价均值乘方案数$n!$

   若$i$对$j$有贡献，那么区间$[i,j]$内必然先删除$i$(与方法1原理相同)。那么$j$产生贡献的期望次数为$\sum\limits_{i=1}^{n}\frac{1}{\mid j-i\mid+1}$，总的答案为$\sum\limits_{j=1}^{n}a_j\sum\limits_{i=1}^{n}\frac{1}{\mid j-i\mid+1}$

GTW likes czf(HDU 5598) 数位Dp

AC代码 （PS. 第一次见循环版数位Dp，感觉思路比递归版更清晰）

对一个大小为$n$数集$S$的每一个元素与$x$亦或，得到的新的数集$S'$大小仍为$n$，即不同的数与$x$亦或后得到的数不同：假设$a\oplus x=b\oplus x$，定有$a=b$。

那么，该题的答案$ans=2(r-l+1)-k$，$k$为满足$a\oplus g=b\oplus t$的数对$(a,b)$的个数。

对式子稍作变换，得到$a\oplus b=g\oplus t$，用数位Dp计数。

记$f(a', b',x)$为$a\in[0,a'],b\in[0,b'],x=g\oplus t$时，满足$a\oplus b=x$的对数。

最终答案为$2(r-l+1)-(f(r,r,x)-2*f(l-1,r,x)+f(l-1,l-1,x))$（容斥）

Little Elephant and Boxes(CodeChef - LEBOXES) MeetInMiddle

$dp[i][j][k]$求出前$i$个物品买了$j$个，用了$k$个钻石时，使用的最少金币数。

接着把左半边的袋子所有可能性跑出来，按钻石数分组，组内按金币数排序。

右半边袋子同样处理。

枚举左半边钻石数$i$，右半边钻石数$j$，购买物品数$k$，双指针扫描两个组即可。

理论AC

Cross-stitch(URAL 1035) 题都没看

AC代码

AtCoder AGC028-B

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

using namespace std;
const int maxn = 1e5 + 100;
const ll mod = 1e9 + 7;

ll n, nfac = 1;
ll a[maxn], presum[maxn];

ll inv(ll base){
    ll t = mod - 2, ret = 1;
    for(; t; t>>=1){
        if(t & 1) ret = ret * base % mod;
        base = base * base % mod;
    }
    return ret;
}

void init(){
    for(int i=2; i<=n; i++) nfac = nfac * i % mod;
    for(int i=2; i<=n; i++){
        presum[i] = (presum[i-1] + nfac * inv(i) % mod) % mod;
    }
}

void solve(){
    cin >> n;
    init();
    ll suma = 0, ans = 0;
    for(int i=1; i<=n; i++) cin >> a[i], suma = (suma + a[i]) % mod;
    for(int i=1; i<=n; i++){
        ans = (ans + (presum[i] + presum[n - i + 1]) % mod * a[i]) % mod;
    }
    ans = (ans + suma * nfac % mod) % mod;
    cout << ans << '\n';
}

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

HDU 5598

1. 递归版数位dp

#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;

int an[64], bn[64], xn[64];
ll dp[64][2][2];
ll calc(int bit, int lim_a, int lim_b){ // 数位dp巨多条件判断
    if(bit == -1) return 1;
    if(~dp[bit][lim_a][lim_b]) return dp[bit][lim_a][lim_b];
    ll & ans = dp[bit][lim_a][lim_b] = 0;
    if(lim_a && lim_b){
        if(xn[bit]){
            if(an[bit]) ans += calc(bit - 1, 1, bn[bit]==0);
            if(bn[bit]) ans += calc(bit - 1, an[bit] == 0, 1);
        }else{
            if(an[bit] && bn[bit]) {
                ans += calc(bit - 1, 0, 0);
                ans += calc(bit - 1, 1, 1);
            }else{
                ans += calc(bit - 1, an[bit]==0, bn[bit]==0);
            }
        }
    }else if(lim_a == 0 && lim_b == 0){
        ans = 2 * calc(bit - 1, 0, 0);
    }else{
        ans += calc(bit - 1, lim_a, lim_b);
        if(lim_a && an[bit]) ans += calc(bit - 1, 0, 0);
        if(lim_b && bn[bit]) ans += calc(bit - 1, 0, 0);
    }
    return ans %= mod;
}

void set_val(ll a, ll b, ll x){
    memset(dp, -1, sizeof dp);
    for(int i=62; i>=0; i--){
        an[i] = a >> i & 1;
        bn[i] = b >> i & 1;
        xn[i] = x >> i & 1;
    }
}

void solve(){
    ll l, r, g, t;
    cin >> l >> r >> g >> t;
    set_val(r, r, g ^ t);
    ll ans = calc(63, 1, 1);
    set_val(r, l - 1, g ^ t);
    ll tmp = calc(63, 1, 1) * 2;
    set_val(l - 1, l - 1, g ^ t);
    ans = ((ans - tmp + mod) % mod + calc(63, 1, 1)) % mod;
    cout << (2 * (r - l + 1) - ans + mod) % mod << '\n';
}

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

2. 循环版

#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;

int an[64], bn[64], xn[64];
ll dp[64][2][2];

void add(ll & val, ll delta){val = (val + delta) % mod;}

ll calc(ll a, ll b, ll x){
    memset(dp, 0, sizeof dp);
    for(int i=62; i>=0; i--){
        an[i] = a >> i & 1;
        bn[i] = b >> i & 1;
        xn[i] = x >> i & 1;
    }
    dp[63][1][1] = 1;
    for(int i=62; i>=0; i--){
        if(an[i] ^ bn[i] == xn[i]) add(dp[i][1][1], dp[i+1][1][1]);
        add(dp[i][1][0], dp[i+1][1][0]);
        if(xn[i] == an[i] && bn[i]) add(dp[i][1][0], dp[i+1][1][1]);
        add(dp[i][0][1], dp[i+1][0][1]);
        if(xn[i] == bn[i] && an[i]) add(dp[i][0][1], dp[i+1][1][1]);
        // dp[i][0][0]可以从[0][0], [0][1], [1][0], [1][1]转移过来
        // 在if()里填入对应条件即可
        add(dp[i][0][0], 2 * dp[i+1][0][0]);
        if(an[i]) add(dp[i][0][0], dp[i+1][1][0]);
        if(bn[i]) add(dp[i][0][0], dp[i+1][0][1]);
        if(an[i] && bn[i] && xn[i]==0) add(dp[i][0][0], dp[i+1][1][1]);
    }
    return (dp[0][0][0] + dp[0][1][0] + dp[0][0][1] + dp[0][1][1]) % mod;
}


void solve(){
    ll l, r, g, t, ans;
    cin >> l >> r >> g >> t;
    ans = (calc(r, r, g ^ t) + calc(l - 1, l - 1, g ^ t) - 2 * calc(r, l - 1, g ^ t) % mod + mod) % mod;
    cout << (2 * (r - l + 1) - ans + mod) % mod << '\n';
}

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