LOJ#565. 「LibreOJ Round #10」mathematican 的二进制

[传送门](https://loj.ac/problem/565)

题解：
考虑怎么做这道题。
首先发现性质：
$改变次数=2\times 总操作数-答案中'1'的个数$
我们考虑怎么统计这两段的期望。
第一段就相当于选那么多个操作的概率乘积的和
可以直接分治$NTT$
考虑 构造多项式$\prod(p_ix+(1-p_i))$
很板。

第二段怎么做呢？
首先转变一下，我们统计每一位是$1$的期望加起来
就等价于最后$1$的个数的期望，这样把统计放到了位上。
考虑我们模拟一次答案时候的操作，
我们可以先把操作放在每一位上，然后一步扫过去进位。
是不是可以采用同样的方法统计呢？
是的，先对每一位求出$f_i$表示这一位只看自己操作有$i$个$1$的概率。
然后考虑一遍扫过去进位。
设$g_i$为每一位考虑进位后的$f_i$
每一次进位相当于用当前的$f_i$算出$f'_i$让$f_i\to f'_{i/2}$
然后把$f'_i$加到下一项去进位，考虑下一项可能进了$1,2,3,4,....,n/2$位，是一个卷积形式，再用一次$NTT$合并即可。
分析复杂度：两边的分治$NTT$部分都是$nlog^2n$
进位操作时，每一个多项式最多贡献$dlogd$个位置，$d$是度数，一个位置贡献$logd$，总复杂度仍然是$nlog^2n$

```
#pragma GCC optimize("O2")
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<vector>
#define LL long long
using namespace std;
const int maxn = 2e5 + 5000;
const int mod = 998244353;
const int G = 3;
int n, a[maxn], p[maxn], m, x, totl;
vector<int > pos[maxn];
void read(int &x) {
	x = 0; static char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
inline int mul(const int &a, const int &b) {
    return (LL)a * b % mod;
}
inline void Add(int &x, const int &a) {
    x += a; if(x >= mod) x -= mod;
}
inline void Dec(int &x, const int &a) {
    x -= a; if(x < 0) x += mod;
}
inline int Plus(const int &a, const int &b) {
	return a + b >= mod ? a + b - mod : a + b;
}
inline int Minus(const int &a, const int &b) {
	return a - b < 0 ? a - b + mod : a - b;
}
int fpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return ans;
}
namespace Poly {
    const int maxd = 1e6 + 5;
    struct PLG {
        vector<int > x;
        int deg() const {return x.size() - 1;}
        void ext(int n) {x.resize(n + 1);}
        void prt() {
            int len = deg();
            for(register int i = 0; i <= len; ++i)
                printf("%d ", x[i]);
            putchar('\n');
        }
    };
    int RL[maxd], N, mxp2, w[maxd];
    void init(int n) {
        for(N = 1, mxp2 = 0; N <= n; N <<= 1, ++mxp2) ;
        for(register int i = 0; i < N; ++i)
            RL[i] = (RL[i >> 1] >> 1) | ((i & 1) << mxp2 - 1);
    }
    void NTT(PLG &A, int type) {
        int tmp, x, y, Wn; 
        A.ext(N);//totl += N;
        for(register int i = 0; i < N; ++i)
            if(i < RL[i]) swap(A.x[i], A.x[RL[i]]);
        for(register int i = 1; i < N; i <<= 1) {
            Wn = fpow(G, (mod - 1) / (i << 1));
            if(type == -1) Wn = fpow(Wn, mod - 2);
            w[0] = 1;
            for(register int j = 1; j <= i; ++j)
                w[j] = mul(w[j - 1], Wn);
            for(register int j = 0, p = i << 1; j < N; j += p) {
                for(register int k = 0; k < i; ++k) {
                    x = A.x[j + k], y = mul(A.x[j + i + k], w[k]);
                    A.x[j + k] = Plus(x, y);
                    A.x[j + i + k] = Minus(x, y);
                }
            }
        }
    }
    PLG operator *(PLG A, PLG B) {
        int len = A.deg() + B.deg();
        init(len);
        NTT(A, 1), NTT(B, 1);
        for(register int i = 0; i < N; ++i)
            A.x[i] = mul(A.x[i], B.x[i]);
        NTT(A, -1);
        int invN = fpow(N, mod - 2);
        for(register int i = 0; i < N; ++i)
            A.x[i] = mul(A.x[i], invN);
        A.ext(len);
        return A;
    }
    PLG operator - (PLG A, const PLG &B) {
        int len = max(A.deg(), B.deg());
        A.ext(len);
        for(register int i = B.deg(); i >= 0; --i)
            Dec(A.x[i], B.x[i]);
        return A;
    }
    PLG operator + (PLG A, const PLG &B) { 
        int len = max(A.deg(), B.deg());
        A.ext(len);
        for(register int i = B.deg(); i >= 0; --i)
            Add(A.x[i], B.x[i]);
        return A;
    }
    void operator %= (PLG &x, const int &l) {
        x.ext(l - 1);
    }
}
Poly::PLG solve(int l, int r) {
    using namespace Poly;
    if(l == r) {
        PLG ret;
        ret.x.push_back((1 - p[l] + mod) % mod);
        ret.x.push_back(p[l]);
        return ret;
    }
    int mid = l + r >> 1;
    return solve(l, mid) * solve(mid + 1, r);
}
Poly::PLG solve_bit(int b, int l, int r) {
    using namespace Poly;
    if(l == r) {
        PLG ret;
        ret.x.push_back((1 - pos[b][l] + mod) % mod);
        ret.x.push_back(pos[b][l]);
        return ret;
    }
    int mid = l + r >> 1;
    return solve_bit(b, l, mid) * solve_bit(b, mid + 1, r);
}
int solve2() {
    using namespace Poly;
    PLG up, now; up.x.push_back(1);
    int ret = 0, l, hf;
    for(register int i = 0; i <= n || up.deg(); ++i) {
        if(pos[i].size()) {
        	now = solve_bit(i, 0, pos[i].size() - 1) * up;
		} else now = up;
		l = now.deg();
        for(register int j = 1; j <= l; j += 2) {
            Add(ret, now.x[j]);
        }
        up.x.clear();
        for(register int j = 0; j <= l / 2; ++j) {
    		up.x.push_back(0);
            Add(up.x[j], now.x[2 * j]);
            if(2 * j + 1 <= l) Add(up.x[j], now.x[2 * j + 1]);
        }   
        //up.prt();
    }
    return ret;
}
int main() {
	//freopen("bin.3.1.in", "r", stdin);
    using namespace Poly;
    read(n), read(m);
    for(register int i = 1; i <= m; ++i) {
        read(a[i]), read(x);
        p[i] = x, read(x);
        p[i] = mul(p[i], fpow(x, mod - 2));
        pos[a[i]].push_back(p[i]);
    }
    int ret = 0;
    //int st = clock();
    PLG ans = solve(1, m);
    //printf("%d\n", clock() - st);
    for(register int i = ans.deg(); i >= 0; --i)
        Add(ret, mul(ans.x[i], i));
    ret = mul(ret, 2);
    Dec(ret, solve2());
    printf("%d", ret);
    return 0;
}

```

Rockdu's Blog

导航

最近发表

大佬们的友链