2023牛客寒假算法基础集训营3 A-I+K

A

题解

知识点:贪心。

把所有正偶数除成奇数,即可。

(人傻了没加 \(x>0\) WA2

时间复杂度 \(O(n)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        while (x > 0 && x % 2 == 0) x /= 2;
        ans += x;
    }
    cout << ans << '\n';
    return 0;
}

B

题解

知识点:数学,构造。

特判 \(n=2\) 无解。

可以先放边长为 \(\left\lceil \dfrac{n}{2} \right\rceil\) 正方形,随后边长每增加 \(1\) 需要最少 \(3\) 块,直到边长为 \(2 \cdot \left\lceil \dfrac{n}{2} \right\rceil\) 后,边长每增加 \(1\) 需要最少 \(5\) 块。以此类推,当边长为 \(\left[(k-1)\cdot\left\lceil \dfrac{n}{2} \right\rceil,k\cdot\left\lceil \dfrac{n}{2} \right\rceil \right),k \in \N^+\) 时,边长每增加 \(1\) 需要 \(2k-1\) 块积木。

显然,摆完第一轮边长为 \(\left\lceil \dfrac{n}{2} \right\rceil\) 后,剩下的 \(n - \left\lceil \dfrac{n}{2} \right\rceil\) 个积木,而 \(\left\lfloor \dfrac{n - \left\lceil \dfrac{n}{2} \right\rceil}{3} \right\rfloor \leq \left\lceil \dfrac{n}{2} \right\rceil\) ,因此不可能摆到需要 \(5\) 个积木的情况。

综上,边长最大值为 \(\left\lceil \dfrac{n}{2} \right\rceil + \left\lfloor \dfrac{n - \left\lceil \dfrac{n}{2} \right\rceil}{3} \right\rfloor\)

本题也可以用二分边长做。

(没考虑 \(n - \left\lceil \dfrac{n}{2} \right\rceil\) 大小,傻了吧唧的算了通式,不过可以出题了qwq

考虑 \(n\) 块积木,给定 \(m\) ,每块积木大小为 \(1 \times k,k \in \left[ 1,\left\lceil \dfrac{m}{2} \right\rceil \right]\) ,求能摆成正方形的边长最大值。

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

bool solve() {
    ll n;
    cin >> n;
    if (n == 2) return false;
    ll a = (n + 1) / 2;
    ll ans = a + (n - a) / 3;
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题解

知识点:构造。

\(n \leq 3\)\(n = 7\) 时无解。

考虑 \(n\bmod 4 = 0,1,2,3\) 的情况。

  1. \(n \bmod 4 = 0\) 时显然形如构造 \(3,4,1,2\) 的循环即可。
  2. \(n \bmod 4 = 1\) 时,前 \(5\) 项构造成 \(4,5,1,2,3\) ,其余仿照 \(n \bmod 4 = 0\) 情况。
  3. \(n \bmod 4 = 2\) 时,前 \(6\) 项构造成 \(4,5,6,1,2,3\) ,其余仿照 \(n \bmod 4 = 0\) 情况。
  4. \(n \bmod 4 = 3\) 时,前 \(11\) 项构造分为 \(5\) 项和 \(6\) 项两组仿照 \(n \bmod 4 = 1,2\) 情况,其余仿照 \(n \bmod 4 = 0\) 情况。

时间复杂度 \(O(n)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

bool solve() {
    int n;
    cin >> n;
    if (n <= 3 || n == 7) return false;
    int m = 1;
    if (n % 4 == 1) {
        cout << "4 5 1 2 3" << ' ';
        m = 6;
    }
    else if (n % 4 == 2) {
        cout << "4 5 6 1 2 3" << ' ';
        m = 7;
    }
    else if (n % 4 == 3) {
        cout << "4 5 1 2 3 9 10 11 6 7 8" << ' ';
        m = 12;
    }
    for (int i = m;i <= n;i += 4) {
        cout << i + 2 << ' ' << i + 3 << ' ' << i << ' ' << i + 1 << ' ';
    }
    cout << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

题解

知识点:博弈论。

这类题需要先对局面分类,每种局面考虑找到一组平衡的操作,即对于其中一人,无论另一人如何操作,他都可以在下一次操作后回到原来的局面。

考虑将 \(n\) 分奇偶情况:

  1. \(n\) 为偶数,小红每次可以选 \(1\) ,随后数变为奇数局面,小紫只有奇数因子能选,数又变为偶数局面。到最后,必然是小紫让数变为 \(0\) ,因为只有小紫能让数变为偶数。因此,偶数局面小红必胜。
  2. \(n\) 为奇数,根据 \(n\) 为偶数的推理,发现奇数局面小红必败。

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n;
    cin >> n;
    if (n & 1) cout << "yukari" << '\n';
    else cout << "kou" << '\n';
    return 0;
}

E

题解

知识点:计算几何。

\(A(x_A,y_A),B(x_B,y_B),C(x_C,y_C)\) 构成等腰直角三角形,其中 \(C\) 为顶点且在 \(AB\) 右侧,满足方程:

\[\left\{ \begin{aligned} x_C+y_C = x_A + y_B\\ x_C-y_C = x_B - y_A \end{aligned} \right. \]

方程可以通过全等三角形证明。

显然 \(C\)\(C\) 关于 \(AB\) 的对称点同时是或不是整数点,解出 \(C(x_C,y_C)\) 后判断是否为整数即可。

(平面几何永远的痛,并且以为无解输出-1收获WA

时间复杂度 \(O(1)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll x = a + d + c - b;
    ll y = a + d + b - c;
    if (x & 1 || y & 1)cout << "No Answer!" << '\n';
    else cout << x / 2 << ' ' << y / 2 << '\n';

    return 0;
}

F

题解

知识点:宇宙的终极答案。

通过你高超的中文流读取技术,发现这是营销号特有的文案。

本打算对此嗤之以鼻的你,阅读完样例后逐渐理解了一切,确信 \(42\) 就是宇宙的终极答案。

时间复杂度 \(O(\infin)\)

空间复杂度 \(O(\infin)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << 42 << '\n';
    return 0;
}

G

题解

知识点:模拟,枚举,dfs。

很简单(痛苦)的模拟。

dfs枚举每个 ? 的三种可能即可,注意快速幂前把底数模一下,因为可能炸 long long

可以选择预处理数字后边枚举边求值,也可以考虑枚举完再求值。注意,边枚举边求值不太适用于有优先级表达式。

(被表达式求值整了一顿,码力太差了QAQ

时间复杂度 \(O(3^{12} \cdot n)\)

空间复杂度 \(O(n)\)

代码

边枚举边求值

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll qpow(ll a, ll k, ll P) {
    ll ans = 1;
    while (k) {
        if (k & 1) ans = ans * a % P;
        k >>= 1;
        a = a * a % P;
    }
    return ans;
}

int ans;
vector<int> num;
vector<char> op(20);
bool dfs(int step = 1, ll cur = num[0]) {
    if (step == num.size()) return cur == ans;
    op[step] = '+';
    if (dfs(step + 1, cur + num[step])) return true;
    op[step] = '-';
    if (dfs(step + 1, cur - num[step])) return true;
    if (cur > 0 && num[step] > 0) {
        op[step] = '#';
        if (dfs(step + 1, qpow(cur % num[step], cur, num[step]))) return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    for (int i = 0;i < s.size();i++) {
        if (isdigit(s[i])) ans = ans * 10 + s[i] - '0';
        else num.push_back(ans), ans = 0;
    }
    if (dfs()) {
        cout << num[0];
        for (int i = 1;i < num.size();i++) cout << op[i] << num[i];
        cout << '=' << ans << '\n';
    }
    else cout << -1 << '\n';
    return 0;
}

枚举完求值,用到表达式计算。

这里给了一个模板,可以修改map的优先级,支持带括号的二元运算,以及伪负号运算(指负号运算必须打括号)。

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

ll qpow(ll a, ll k, ll P) {
    ll ans = 1;
    while (k) {
        if (k & 1) ans = ans * a % P;
        k >>= 1;
        a = a * a % P;
    }
    return ans;
}

map<char, int> mp = { {'+',0},{'-',0},{'#',0},{'=',0} };
bool calc(string s) {
    vector<ll> num = { 0 };
    vector<char> op;
    for (auto ch : s) {
        if (ch >= '0' && ch <= '9') num.back() = num.back() * 10 + ch - '0';
        else {
            while (op.size() && mp[ch] <= mp[op.back()]) {
                char ope = op.back();
                op.pop_back();
                ll x = num.back();
                num.pop_back();
                if (ope == '+') num.back() += x;
                else if (ope == '-') num.back() -= x;
                else if (ope == '#') {
                    if (x <= 0) return false;
                    num.back() = qpow(num.back() % x, num.back(), x);
                }
            }
            if (ch == '#' && num.back() <= 0) return false;
            op.push_back(ch);
            num.push_back(0);
        }
    }
    return num[0] == num[1];
}

string s;
bool dfs(int step = 0) {
    if (step == s.size()) return calc(s);
    if (s[step] == '?') {
        s[step] = '+';
        if (dfs(step + 1)) return true;
        s[step] = '-';
        if (dfs(step + 1)) return true;
        s[step] = '#';
        if (dfs(step + 1)) return true;
        s[step] = '?';
    }
    else {
        while (step < s.size() && s[step] != '?') step++;
        if (dfs(step)) return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s;
    if (dfs()) cout << s << '\n';
    else cout << -1 << '\n';
    return 0;
}

H

题解

知识点:概率dp。

可能重要的前置知识(大佬请跳过)

对于一维期望dp,在第 \(i\) 步时,其向其他状态转移的起点只有 \(f_i\) 一种,因此在第 \(i\) 步起点是状态 \(f_i\) 的概率是百分百的,变化的期望直接加就行。

例如,有期望状态 \(f_i\) 。操作有两种,概率分别为 \(\dfrac{1}{4},\dfrac{3}{4}\),两种操作的贡献分别是 \(1,3\) 。那么可以有转移方程:

\[f_{i+1} = \dfrac{1}{4}(f_i+1) + \dfrac{3}{4}(f_i+3) \]

但是,如果在一维期望dp的基础上,设每一步都有多个不同的状态,那么转移时的期望就不是简单加法了。

具体的说,在第 \(i\) 步时,其向其他状态转移的起点如果是 \(f_{i,j}\)\(j\) 种,那么显然这 \(j\) 种状态都有概率成为起点,满足概率的总和为百分百。因此考虑 \(f_{i,j}\) 为起点做转移时,变化的期望需要乘上其作为起点的概率,表示这步操作在 \(f_{i,j}\) 作为起点的概率下的期望。当然,期望 \(f_{i,j}\) 本身不需要再乘一遍概率,因为求这个期望时已经考虑了到这个状态的概率,同时我们还可以知道这 \(j\) 种期望的总和就是第 \(i\) 步的总期望。

例如,有期望状态 \(f_{i,0/1/2}\) ,设 \(f_{i,j}\) 的概率为 \(g_{i,j}\) 。操作有两种,概率分别为 \(\dfrac{1}{4},\dfrac{3}{4}\) ,我们假设从 \(f_{i,0/2}\) 都可以通过两种操作转移到 \(f_{i+1,0}\) ,两种操作的贡献对于两种状态分别是 \(1,2\)\(5,6\) 。那么对于 \(f_{i+1,0}\) 可以有转移方程:

\[\begin{aligned} f_{i+1,0} &= \dfrac{1}{4}(f_{i,0} + 1\cdot g_{i,0}) + \dfrac{3}{4}(f_{i,0} + 2 \cdot g_{i,0})\\ &+\dfrac{1}{4}(f_{i,2} + 5\cdot g_{i,2})+\dfrac{3}{4}(f_{i,2} + 6 \cdot g_{i,2}) \end{aligned} \]

接下来就可以轻松(真的吗)做这道题了。

\(f_{i,j,k}\) 为执行到第 \(i\) 步且满足串首状态为 \(j\) 、串尾状态为 \(k\) 的期望个数。其中,\(j = 0/1\) 表示串首是 rededr\(k = 0/1\) 同理。

\(g_{i,j,k}\) 为对应的 \(f_{i,j,k}\) 发生的概率。注意,除了四种串首尾的状态,还有一种空串的状态,这里没有标记到数组里,但是每步还是得自己手动加上去的,我们记 \(prob\) 为空串的概率,空串的期望为 \(0\) 不需要考虑。

因此有转移方程:

\[\left\{ \begin{aligned} f_{i+1,0,0} &= \frac{1}{3} \cdot ((0 + 1 \cdot prob) + (f_{i,0,0} + 1 \cdot g_{i,0,0})+(f_{i,0,1}+1\cdot g_{i,0,1}))\\ &+ \frac{1}{3} \cdot 0\\ &+ \frac{1}{3} \cdot (10 \cdot f_{i,0,0})\\ f_{i+1,0,1} &= \frac{1}{3} \cdot 0\\ &+ \frac{1}{3} \cdot ((f_{i,0,0} + 0 \cdot g_{i,0,0})+(f_{i,0,1}+1 \cdot g_{i,0,1}))\\ &+ \frac{1}{3} \cdot (10\cdot f_{i,0,1})\\ f_{i+1,1,0} &=\frac{1}{3} \cdot ((f_{i,1,0} + 1 \cdot g_{i,1,0})+(f_{i,1,1}+1 \cdot g_{i,1,1}))\\ &+\frac{1}{3} \cdot 0\\ &+\frac{1}{3} \cdot (10 \cdot f_{i,1,0})\\ f_{i+1,1,1} &= \frac{1}{3} \cdot 0\\ &+ \frac{1}{3} \cdot ((0 + 0 \cdot prob) + (f_{i,1,0} + 0 \cdot g_{i,1,0})+(f_{i,1,1}+1 \cdot g_{i,1,1}))\\ &+ \frac{1}{3} \cdot (10 \cdot f_{i,1,1} + 9 \cdot g_{i,1,1})\\ g_{i+1,0,0} &= \frac{1}{3} \cdot (prob + g_{i,0,0} + g_{i,0,1}) + \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot g_{i,0,0}\\\ g_{i+1,0,1} &= \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot (g_{i,0,0} + g_{i,0,1}) + \frac{1}{3} \cdot g_{i,0,1}\\\ g_{i+1,1,0} &= \frac{1}{3} \cdot (g_{i,1,0} + g_{i,1,1}) + \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot g_{i,1,0}\\\ g_{i+1,1,1} &= \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot (prob + g_{i,1,0} + g_{i,1,1}) + \frac{1}{3} \cdot g_{i,1,1}\\\ prob' &= \frac{1}{3} \cdot prob \end{aligned} \right. \]

写的很详细了,三个 \(\dfrac{1}{3}\) 对应三种操作,分别算一下概率和期望转移就行。特别注意,\(f_{i+1,1,1}\) 的操作三转移可以产生十倍加九的期望。

代码用滚动数组压缩了一维, \(f_{j,k,0/1}\) 代表第 \(i\) 步的各种概率/期望, \(g_{j,k,0/1}\) 代表第 \(i+1\) 步的各种概率/期望。并且,代码转移时是用子状态刷表,而非如上述转移方程填表,因为写起来比较方便。填表也能写,本质都是一样的,很好理解。

推荐使用 Modint 不然开 long long 也救不了打 % 打到手酸。

时间复杂度 \(O(k)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

const int P = 1e9 + 7;
struct Modint {
    int val;
    Modint(int _val = 0):val(_val %P) { format(); }
    Modint(ll _val):val(_val %P) { format(); }

    //if val in [-P,2P)
    //maybe slower than global version
    Modint &format() {
        if (val < 0) val += P;
        if (val >= P) val -= P;
        return *this;
    }
    Modint inv()const { return qpow(*this, P - 2); }

    Modint &operator+=(const Modint &x) { val += x.val;return format(); }
    Modint &operator-=(const Modint &x) { val -= x.val;return format(); }
    Modint &operator*=(const Modint &x) { val = 1LL * val * x.val % P;return *this; }
    Modint &operator/=(const Modint &x) { return *this *= x.inv(); }
    friend Modint operator-(const Modint &x) { return { -x.val }; }
    friend Modint operator+(Modint a, const Modint &b) { return a += b; }
    friend Modint operator-(Modint a, const Modint &b) { return a -= b; }
    friend Modint operator*(Modint a, const Modint &b) { return a *= b; }
    friend Modint operator/(Modint a, const Modint &b) { return a /= b; }

    friend Modint qpow(Modint a, ll k) {
        Modint ans = 1;
        while (k) {
            if (k & 1) ans = ans * a;
            k >>= 1;
            a = a * a;
        }
        return ans;
    }

    friend istream &operator>>(istream &is, Modint &x) {
        ll _x;
        is >> _x;
        x = { _x };
        return is;
    }
    friend ostream &operator<<(ostream &os, const Modint &x) { return os << x.val; }
};
/*
f[0/1][0/1][0]:概率
f[0/1][0/1][1]:期望
00  red-red
01  red-edr
10  edr-red
11  edr-edr
注意还有一种空串情况
需要每次操作前手动加
*/
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int k;
    cin >> k;
    array<array<array<Modint, 2>, 2>, 2> f = {};
    Modint inv3 = Modint(3).inv();
    Modint prob = 1;
    for (int i = 1;i <= k;i++) {
        //prod指空串概率,空串期望始终为0不需要管
        array<array<array<Modint, 2>, 2>, 2> g = {};
        g[0][0][0] = inv3 * prob;
        g[1][1][0] = inv3 * prob;
        g[0][0][1] = inv3 * prob;
        //空串到g[1][1]的期望还是0,不用管
        for (auto i : { 0,1 }) {
            for (auto j : { 0,1 }) {
                g[i][0][0] += inv3 * f[i][j][0];//操作1后的概率
                g[i][1][0] += inv3 * f[i][j][0];//操作2后的概率
                g[i][j][0] += inv3 * f[i][j][0];//操作3后的概率

                g[i][0][1] += inv3 * f[i][j][1];//操作1后的期望
                g[i][0][1] += inv3 * f[i][j][0];
                g[i][1][1] += inv3 * f[i][j][1];//操作2后的期望
                if (j == 1) g[i][1][1] += inv3 * f[i][j][0];//只有?1才能加
                g[i][j][1] += 10 * inv3 * f[i][j][1];//操作3后的期望
                if (i == 1 && j == 1) g[i][j][1] += 9 * inv3 * f[i][j][0];//只有11能加9个
            }
        }
        prob *= inv3;
        f = g;
    }
    Modint sum = 0;
    for (auto i : { 0,1 })for (auto j : { 0,1 }) sum += f[i][j][1];
    cout << sum << '\n';
    return 0;
}

I

题解

知识点:数论,构造。

  1. 偶数情况,若 \(x-1\) 是素数构造 \(n = (x-1)^2\) ,则 \(f(n) = 1+x-1=x\) ; 若 \(x-3\) 是素数构造 \(n = 2(x-3)\) ,则 \(f(n) = 1+2+x-3=x\)

  2. 奇数情况,因为一定存在 \(1\) 因子,我们考虑使其他因子的和凑出一个偶数 \(x-1\) 。考虑最简单的素数情况,因为哥德巴赫猜想,一个大于等于 \(4\) 的偶数可以被分解成两个素数之和,我们只要找到两个不同的素数 \(p,q\) 使得 \(p+q = x-1\) ,那么构造 \(n = pq\) ,则 \(f(n) = 1+p+q=x\)

    注意,哥德巴赫猜想所述是两个素数之和,不是两个不同的素数。经过测试 int 范围内,大于等于 \(8\) 的偶数都可以被分解为两个不同的素数之和,因此大于等于 \(9\) 的奇数我们无脑无解即可。

    我们需要特判 \(x = 1,3,7\) ,因为这些情况确实有解,但不能通过哥德巴赫猜想构造。

时间复杂度 \(O(x)\)

空间复杂度 \(O(x)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
bool vis[N];
vector<int> prime;
void get_prime(int n) {
    for (int i = 2;i <= n;i++) {
        if (!vis[i]) prime.push_back(i);
        for (int j = 0;j < prime.size() && i * prime[j] <= n;j++) {
            vis[i * prime[j]] = 1;
            if (!(i % prime[j])) break;
        }
    }
}

bool solve() {
    int x;
    cin >> x;
    if (x == 1) {
        cout << 2 << '\n';
        return true;
    }
    if (x == 3) {
        cout << 4 << '\n';
        return true;
    }
    if (x == 7) {
        cout << 8 << '\n';
        return true;
    }
    if (x & 1) {
        for (int i = 0;i < prime.size() && 2 * prime[i] < x - 1;i++) {
            if (!vis[x - 1 - prime[i]]) {
                cout << 1LL * prime[i] * (x - 1 - prime[i]) << '\n';
                return true;
            }
        }
    }
    else {
        if (!vis[x - 1]) cout << 1LL * (x - 1) * (x - 1) << '\n';
        else cout << 1LL * 2 * (x - 3) << '\n';
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    get_prime(1e6);
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

K

题解

知识点:贪心,数学。

给你前 \(n\) 种素数,每个素数有 \(a_i\) 个。

\(size = \sum_{i=1}^n a_i\) 。现在将这 \(size\) 个素数排成一个序列,设 \(f(i)\) 为序列中 \([1,i]\) 的数的乘积的因子的数量。现在求 \([1,size]\)\(f(i)\) 的和,即 \(\sum_{i=1}^{size} f(i)\) ,的最大值。

显然,我们需要尽可能让前面的 \(f(i)\) 的越大越好。我们知道,乘积的因子数量等于各个素数个数加 \(1\) 的乘积,通过一些尝试很容易发现均摊素数的个数,比连续安排同一种素数得到的结果要大很多,因此我们每次安排还能安排的素数中出现次数最小的那个素数。

我们设 \(cnt_i\) 表示出现至少 \(i\) 次的素数个数,我们发现 \(f(i)\) 的结果呈现 \(2,2^2,\cdots,2^{cnt_1},2^{cnt_1-1} \cdot 3,\cdots,2^{cnt_1-cnt_2} \cdot 3^{cnt_2},\cdots\) 。直接求和要加 \(size\) 次是不可行的,因此我们先用差分维护好 \(cnt_i\) ,随后用等比公式对每 \(cnt_i\) 个数直接求和。

\(pre\)\(cnt_{i-1}\) 段的最后一个数字,那么 \(cnt_i\) 段的总和为 \(pre \cdot \dfrac{1-\frac{i+1}{i}^{cnt_i}}{1-\frac{i+1}{i}}\) ,最后一个数字 \(pre' = pre \cdot \dfrac{i+1}{i}^{cnt_i}\) ,于是就可以递推求和了。

时间复杂度 \(O(2 \cdot 10^5 + n)\)

空间复杂度 \(O(2 \cdot 10^5)\)

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

const int P = 1e9 + 7;
ll qpow(ll a, ll k) {
    ll ans = 1;
    while (k) {
        if (k & 1) ans = ans * a % P;
        k >>= 1;
        a = a * a % P;
    }
    return ans;
}

ll inv(ll a) { return qpow(a, P - 2); }

int cnt[200007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        cnt[1]++;
        cnt[x + 1]--;
    }
    for (int i = 1;i <= 2e5;i++) cnt[i] += cnt[i - 1];
    int pre = 1;
    int ans = 0;
    for (int i = 1;i <= 2e5;i++) {
        int f = 1LL * (i + 1) * inv(i) % P;
        int g = qpow(f, cnt[i]);
        ans = (ans + 1LL * pre * f % P * (1 - g + P) % P * inv(1 - f + P) % P) % P;
        pre = 1LL * pre * g % P;
    }
    cout << ans << '\n';
    return 0;
}

本文来自博客园,作者:空白菌,转载请注明原文链接:http://www.cnblogs.com/BlankYang/p/17066469.html

本文转载于网络 如有侵权请联系删除

相关文章

  • SQL函数 PI

    SQL函数PI返回pi常数值的标量数值函数。大纲{fnPI()} {fnPI}复制描述PI不接受参数。 它返回数学常数pi作为数据类型NUMERIC,精度为19,刻度为18。PI只能使用ODBC标量函数(花括号)语法调用。 请注意,参数括号是可选的。描述下面的例子都返回pi的值:SELECT{fnPI()}ASExactPi 3.141592653589793238复制SELECT{fnPI}ASExactPi 3.141592653589793238复制

  • Java使用FreeMarker模版技术动态生成word实践

    一、序言在日常开发中,常常有动态word文件生成的需求,通过编制模版,然后动态修改word内容以组合成新的文件。报告单、请假单、发票页等都可以使用动态生成word来解决。笔者总结归纳出通用技术要点,尽可能降低广大开发者的使用技术门槛。二、制作与渲染模版(一)总体流程1、准备数据通过查询数据库获取需要修改的数据,或者是调用远程API接口获得数据,数据准备完毕后,进入下一步。2、制作word模版新建并设计出期望效果的word文档样式,包含字体、字号、段落样式布局等,先做出一个静态的word文件。3、制作freemark模版在新建word模版的基础上,使用freemark语法,结合已经准备填充的数据结构,将需要动态变化的内容用变量表示。用变量替换时常见的情形时对象属性和循环。freemark模版制作完成后,保存为ftl后缀文件。4、渲染字符串将数据和freemark模版组合,并且将前期制作的变量占位符替换,形成最终的word文件(二)编码实践按照笔者提供的流程和SDK编码实践相对比较简单。1、引入依赖如下依赖包含封装的工具方法,大幅降低使用门槛。<dependency> <

  • RTSP协议视频监控智能分析平台EasyNVR如何将音频转化为aac格式并上传?

    在之前的博文中,我们和大家分享了使用EasyNVR视频监控直播平台时,如何实现自定义直播背景音乐,在该文中我们知道可以通过拉流库融合的方式推送。但是在实际的应用过程中,我们发现上传的不同格式的音频的实际效果是不一样的,经过多次测试,我们可以确定aac的音频格式是效果最好的。那么如何在音频的使用中使加入的音频是aac的格式呢?这里有两种方法可以实现,下面就分享一下。1、系统转化上传音频文件的时候,可以无需特意关注上传的音频格式,直接由系统服务将音频转化为aac使用。但是该做法的弊端在于,转化的操作都是由服务器自主进行的,假如服务器的硬件性能有瓶颈,则会影响其他服务的使用效果。2、手动转化该方式就是通过我们内置的软件工具将音频格式先手动的转换成aac格式,再将转换好的音频上传到直播中,伴随视频直播使用。转换方式:将需要转换的音频copy到软件包根目录,使用软件包根目录的ffmpeg来进行文件的转换。转换命令:ffmpeg-ixxx.mp3-acodecaac-strictexperimental-ab128k-ar16k-ac2-yxxx.aac复制参数定义: ab:码率 ar:采样率 a

  • Win10安装配置Windows Terminal

    先导本文也是在Win10主机下配置轻量级开发环境的一个帖子,主要是用来记录Win10下的新WindowsTerminal的安装和配置,留作以后参考 安装直接在Win10商店中安装WindowsTerminal即可配置WindowsTerminal的配置基本上是直接配置它的配置文件进行的,该文件通过它的配置按钮调出,有系统默认的json文本编辑器进行编辑字体字体的配置需要在profile节点中的default进行编辑JetBrainsMono字体JetBriansMono字体是由JetBrains公司开发的一款开源等宽字体,它旗下的产品在业内的知名度人尽皆知,所以这款字体也是和它的老大哥CLion等一样是很硬的存在,非常推荐使用该字体 配置配置如下"defaults": { //Putsettingsherethatyouwanttoapplytoallprofiles. "cursorHeight":25, "fontFace":"JetBrainsMono", "fontSize":1

  • 常见的50道数据库面试题

    前言:2021年的第一篇公众号,希望自己在学到知识的同时也能分享给大家,一起进步!! 今年目标:每天多学习,多积累,多分享50个常用sql语句学生表Student(S#,Sname,Sage,Ssex)课程表Course(C#,Cname,T#)成绩表SC(S#,C#,score)教师表Teacher(T#,Tname)1、查询“001”课程比“002”课程成绩高的所有学生的学号;selecta.S#from(selectS#,scorefromSCwhereC#='001')a,(selectS#,scorefromSCwhereC#='002')bwherea.score>b.scoreanda.S#=b.S#;2、查询平均成绩大于60分的同学的学号和平均成绩;selectS#,avg(score)fromSCgroupbyS#havingavg(score)>60;3、查询所有同学的学号、姓名、选课数、总成绩;selectStudent.S#,Student.Sname,count(SC.C#),sum(score)fromSt

  • docker学习15-Docker 使用修改后容器来创建镜像

    前言前面讲通过Dockefile可以制作自己的镜像,通过镜像创建容器启动服务,有时候需要修改容器里面的内容,比如我们想改点BUG。 我们可以直接在容器里面修改,验证通过后,基于现有的容器创建一个新的镜像。dockercommitdockercommit命令是从容器创建一个新的镜像,基本语法dockercommit[OPTIONS]容器名称或id镜像名称:tagPTIONS参数说明: -a:提交的镜像作者; -c:使用Dockerfile指令来创建镜像; -m:提交时的说明文字; -p:在commit时,将容器暂停。修改容器内容先通过基础镜像,启动一个容器后[root@VM_0_2_centos~]#dockerimages django_yoyolatest984e5b0a98967weeksago1.2GB [root@VM_0_2_centos~]#dockerrun-d-p8004:8000--nameweb_yoyo1django_yoyo 874813d5c13fa002f6c5886a6b4c2cbc7d96639a3c8ef4de9154d4352b61b70b复制doc

  • R语言对回归模型进行协方差分析

    原文链接:http://tecdat.cn/?p=9529怎么做测试具有两个类别和II型平方和的协方差示例的分析本示例使用II型平方和。参数估计值在R中的计算方式不同, Data=read.table(textConnection(Input),header=TRUE)复制plot(x=Data$Temp,y=Data$Pulse,col=Data$Species,pch=16,xlab="Temperature",ylab="Pulse")legend('bottomright',legend=levels(Data$Species),col=1:2,cex=1,pch=16)复制协方差分析AnovaTable(TypeIItests)SumSqDfFvaluePr(>F)Temp4376.111388.839<2.2e-16***Species598.01189.7899.907e-14***Temp:Species4.311.3570.2542###Interactionisnotsignificant,so

  • 测试开发面试题解

    新书速递 吴老的java版《seleniumwebdriver3实战宝典》和python版《seleniumWebdriver3.0自动化测试框架实战指南》出版了,代码拿来就能用。文|李兴题目描述给定一个由括号元素'(',')','[':,']','{','}'组成的字符串,判断该字符串中的所有类型的括号是否是闭合的。判断条件:(1)左括号必须用相同类型的右括号闭合(2)左括号必须以相同的顺序闭合示例:输入:()输出:true输入:()[]{}输出:true输入:(]输出:false输入:([)]输出:false输入:([{}])输出:true输入:((()))输出:true输入:([[()()]{}]){}[]输出:true 解题分析一通过观察示例中的字符串发现,一个符合括号闭合要求的字符串有如下特点:(1)合理的嵌套关系(2)嵌套的最内层是一对闭合的括号类型(相邻两个元素),如()首先将字符串string转换成列表string_list,然后判断列表string_

  • 浅谈“智慧水泥”

      进入二十一世纪,中国水泥工业取得了巨大进步,全面进入了新型干法的时代。党的十八大提出了生态文明建设的任务,作为传统产业的水泥工业必须加快转变发展方式。利用高新技术改造传统水泥产业,推动行业技术创新,是我国水泥工业转型升级的必然选择水泥工业发展已经进入了一个新阶段。  何谓“智慧水泥”?智慧水泥是基于物联网、云计算、移动互联等新一代信息技术,营造有利于创新涌现的生态,实现全面透彻的感知、宽带泛在的互联、智能融合的应用。  从技术发展的视角看,智慧水泥建设要求通过以移动互联技术为代表的物联网、云计算等新一代信息技术应用实现全面感知、泛在互联和融合应用;强调通过价值创造、以人为本,实现水泥企业经济、社会、环境的全面可持续发展。  智慧水泥为水泥行业安全生产管理提供了先进技术手段,有效弥补传统方法和技术在监管中的缺陷,实现对人、机、料、法、环的全方位实时监控,变被动“监督”为主动“监控”。应用场景  安全帽佩戴检测智慧水泥  周界入侵检测智慧水泥  烟火检测智慧水泥  财产防盗检测智慧水泥  皮带运动检测智慧水泥  工装识别智慧水泥

  • 【DB笔试面试447】AUTHID CURRENT_USER的作用是什么?

    题目部分AUTHIDCURRENT_USER的作用是什么?答案部分这里首先需要明白定义者权限和调用者权限的区别。定义者权限(DifinerRight):定义者权限是程序的默认权限。如果是在用户A下创建的程序,但其他用户只要能执行这个程序,那么这个程序所执行的任务都是以用户A的名义来执行的。因为用户A是程序的定义者。用户A能做什么,那这个程序就能做什么。调用者权限(InvokerRight):也叫执行者权限。如果某个程序中含有创建表的操作,且这个表只有用户A有创建权限,那么这个程序在用户A下面才执行成功,在其他用户下是不能成功执行的。程序中没有AUTHIDCURRENT_USER表示定义者权限,以定义者身份执行;程序中加上AUTHIDCURRENT_USER表示调用者权限,以调用者身份执行。调用者权限与定义者权限之间的差异主要体现在三个方面:1、执行的SCHEMA不同,操作的对象也不同l在定义者权限下,执行的用户为定义者,所操作的对象是定义者在编译时指定的对象。l在调用者权限下,执行的用户为当前用户,所操作的对象是当前模式下的对象。2、执行的权限不同l在定义者权限下,当前用户的权限为角色

  • 1500行TypeScript代码在React中实现组件keep-alive

    现代框架的本质其实还是Dom操作,今天看到一句话特别喜欢,不要给自己设限,到最后,大多数的技术本质是相同的。例如后端用到的Kafka,redis,sql事务写入,Nginx负载均衡算法,diff算法,GRPC,Pb协议的序列化和反序列化,锁等等,都可以在前端被类似的大量复用逻辑,即便js和Node.js都是单线程的认真看完本文与源码,你会收获不少东西框架谁优谁劣,就像Web技术的开发效率与Native开发的用户体验一样谁也不好一言而论谁高谁低,不过可以确定的是,web技术已经越来越接近Native端体验了作者是一位跨平台桌面端开发的前端工程师,由于是即时通讯应用,项目性能要求很高。于是苦寻名医,为了达到想要的性能,最终选定了非常冷门的几种优化方案拼凑在一起过程虽然非常曲折,但是市面上能用的方案都用到了,尝试过了,但是后面发现,极致的优化,并不是1+1=2,要考虑业务的场景,因为一旦优化方案多了,他们之间的技术出发点,考虑的点可能会冲突。这也是前端需要架构师的原因,开发重型应用如果前端有了一位架构师,那么会少走很多弯路。后端也是如此Vue.js中的keep-alive使用:在Vue.js

  • BATJ面试必会之 Spring 篇(三)

    出自:https://www.cnblogs.com/wang-meng/p/5701982.html 整理排版:微信公众号:程序员乔戈里复制1.谈谈你对springIOC和DI的理解,它们有什么区别? IoCInverseofControl反转控制的概念,就是将原本在程序中手动创建UserService对象的控制权,交由Spring框架管理,简单说,就是创建UserService对象控制权被反转到了Spring框架DI:DependencyInjection依赖注入,在Spring框架负责创建Bean对象时,动态的将依赖对象注入到Bean组件 面试题:IoC和DI的区别?IoC控制反转,指将对象的创建权,反转到Spring容器,DI依赖注入,指Spring创建对象的过程中,将对象依赖属性通过配置进行注入2.BeanFactory接口和ApplicationContext接口有什么区别?-①ApplicationContext接口继承BeanFactory接口,Spring核心工厂是BeanFactory,BeanFactory采取延迟加载,第一次getBean时才会初始化Bean,

  • SOA体系结构基础培训教程-规范标准篇

    引子:本文是《SOA体系结构基础培训教程》第3章《SOA标准与规范》课件,版权所有,转载请注明出处。随着SOA在业界的应用日益广泛,SOA的标准化问题也成为各界日益关注的焦点。但是由于国际标准的不统一,给SOA的应用带来了不小的麻烦。好在中国SOA标准化小组的工作得到了普遍的认可,现在已经有部分标准通过了审核,确立了国家标准的地位。其中包括《信息技术面向服务的体系结构(SOA)术语》,《信息技术面向服务的体系结构(SOA)应用的总体技术要求》已经于2013年6月正式生效。本文旨在介绍SOA标准与规范的国际组织、国际标准,我国标准化组织,我国的SOA标准体系结构和当前SOA标准发展现状。 不知道什么原因,居然有些图片无法显示。

  • 【技巧】ionic3独享滚动区域之滑动segment

    好久没写ionic相关内容,写一篇吧。想象一下这样一个场景,通过segment切换页面,通过*ngIf等类似指令来模拟显示不同页面的内容,代码表示如下: <ion-content> <div*ngIf="vm.selectedSegment==1"> 列表1 </div> <div*ngIf="vm.selectedSegment==2"> 列表2 </div> </ion-content>复制其实这两个列表是公用ion-content的滚动条的,也就是说,当列表1滚动到一定距离,当切换到列表2显示时,列表2已滚动到列表1所在的位置了(效果图我就不上了),鉴于此,我们可以在每个div外面再包一层,此层的滚动区域代替ion-content的滚动区域。在这里,我示范使用ion-slides作为容器层来实现:html部分:<ion-headerno-border> <ion-toolbar> <ion-segmentmode="md"

  • 漫谈Web缓存架构

    计算机领域多处地方用到缓存,比如说为了缓解CPU和内存之间的速度不匹配问题,我们往往通过增加一级、二级、三级缓存,CPU先从缓存中取指令,如果取不到,再从内存中取,并更新缓存,同时,根据程序的局部性原理,使得大部分情况下缓存都会命中。目前,Web应用的核心数据通常存放在数据库中,比如说用户信息、订单信息、交易信息等,同时,数据库和编程语言是无关的,通过SQL交互,Java、Php等语言写的程序需要访问数据库,执行业务逻辑,展示结果给用户。但是数据库有一定的局限性,譬如:1.数据库连接是非常"昂贵"的资源,为了复用这些资源,目前采用连接池技术,2.连接池的连接数是有限的,如果用户过多,势必要等待,3.读写数据时需要加锁。通过上述介绍,我们知道一个大型系统中数据库往往会成为瓶颈,我们不能每次访问都访问数据库,尤其是在多用户,大并发的情况下。面对这种情况,我们通常采用何种方法呢?在计算机行业中的所有问题,都可以通过增加一个抽象层来解决。那么,针对数据库这个瓶颈,我们可以在应用层和数据库层增加一层,即缓存层。如何实现缓存如果你是某某大型公司的首席架构师,现在公司需要自研一套

  • VeeR开放编辑/分享SDK:可拥有 iphone X 增强现实效果

    随着全球范围内VR全景爱好者的增多、VR全景内容生产的门槛降低,VeeR也迅速成为VR全景内容增长最快的全球化平台;为推进VR全景行业的发展,VeeR愿为相机厂商提供开放平台,发挥VR全景垂直领域覆盖的领先优势,与相机厂商强强联合,实现用户共享、技术互补。VeeR为相机软件开发者提供开放SDK接口服务,为相机用户打造分享及交流的平台,通过与相机App集成SDK,实现全景内容一键上传,将拍摄、编辑、社交完美结合。此外,通过相机App上传VeeR的作品都自带相机专属标签,帮助增强品牌露出,对品牌长线发展极具战略意义。-VeeR分享SDK-VeeR分享SDK,它允许任何360相机的拍摄素材一键分享到VeeR平台,并在分享页面中自动生成带有相机品牌的标签。大量带有Gear360标签的内容它的好处显而易见:免费使用,支持图片、视频分享;相较API接入更方便;增强相机品牌的曝光;允许相机用户享受便捷的分享体验;支持iOS和安卓系统。接入SDK后,用户可直接在相机App中将全景素材分享至VeeR,简单编辑标题摘要后,即可在VeeR界面看到带有相机标签的作品。【如何获得】VeeR分享SDK,将面对所有

  • redis 学习笔记(6)-cluster集群搭建

    上次写redis的学习笔记还是2014年,一转眼已经快2年过去了,在段时间里,redis最大的变化之一就是cluster功能的正式发布,以前要搞redis集群,得借助一致性hash来自己搞sharding,现在方便多了,直接上cluster功能就行了,而且还支持节点动态添加、HA、节点增减后缓存重新分布(resharding)。下面是参考官方教程cluster-tutorial 在mac机上搭建cluster的过程:一、下载最新版redis编译目前最新版是3.0.7,下载地址:http://www.redis.io/download编译很简单,一个make命令即可,不清楚的同学,可参考我之前的笔记:redis学习笔记(1)-编译、启动、停止二、建6个目录mkdir~/app/redis-cluster/#先建一个根目录 mkdir700070017002700370047005复制注:与大多数分布式中间件一样,redis的cluster也是依赖选举算法来保证集群的高可用,所以类似ZK一样,一般是奇数个节点(可以允许N/2以下的节点失效),再考虑到每个节点做Master-Slave互为备

  • 蓝海讯通年中总结大会,陈旭总结2018上半年工作要点

    2018年7月12日,北京蓝海讯通(OneAPM)在西安召开为期两天的年中总结大会,CEO陈旭,CTO朱凤涛,客户支持中心VP高科等高管团队及20多名中层管理成员参加。 结束冬藏,全力秋收 CEO陈旭就2018年上半年公司经营数据,营销情况及下半年公司战略进行了总结汇报。陈旭表示,公司经过2017年的冬藏,2018年已经进入了春生夏长的状态。 1.虽然公司目前还存在一些问题,但是随着产品质量和用户满意度的逐步提高,公司连续签订了中国移动总部、中国移动互联网公司、云南移动、银华基金、昆明航空、贵州广电、安徽福彩等多个重量级用户。 2.回款额和收入额呈良性递增趋势:公司2018年上半年营业收入同比增长达64%。 3.公司重视关键技术的知识产权固化和保护,2018年上半年,共计获得四项发明专利授权。 4.继续保持较高水平的研发投入,保障产品的持续创新能力,APM团队探索全量数据采集能力,AIOps 人工智能运维平台I2将持续重度投入,完善 ITOM 的整体布局。 5.运营精细化:高度重视团队培养,高度重视项目交付,尽一切努力让所有客户100%满意,全面拓展合作

  • 软件测试常考面试题-软件测试面试宝典(一篇足矣)

    问:软件测试的原则? 答: 1.所有测试的标准都是建立在用户需求之上 2.始终保持“质量第一”的觉悟,当时间和质量冲突时,时间要服从质量 3.需求阶段应定义清楚产品的质量标准 4.软件项目一启动,软件测试就已经开始,而不是等程序写完,才开始进行测试 5.第三方进行测试会更客观,更有效 6.软件测试计划是做好软件测试工作的前提 7.测试用例是设计出来的,不是写出来的 8.对发现错误较多的程序段,应进行更深入的测试 问:你在测试中发现了一个 bug,但是开发经理认为这不是一个 bug,你应该怎样解决。 1、将问题提交到缺陷管理库里面进行备案。2、要获取判断的依据和标准:根据需求说明书、产品说明、设计文档等,确认实际结果是否与计划有不一致的地方,提供缺陷是否确认的直接依据;如果没有文档依据,可以根据类似软件的一般特性来说明是否存在不一致的地方,来确认是否是缺陷;根据用户的一般使用习惯,来确认是否是缺陷;3、与设计人员、开发人员和客户代表等相关人员探讨,确认是否是缺陷;4、合理的论述,向测试经理说明自己的判断的理由,注意客观、严谨,不参杂个人情绪。等待测试经理做出最终决定,

  • ubuntu 16.04安装笔记

    这是一篇在Ubuntu下发布的日志,updatedate:2017.01.19 -------------------------------------------------------- 昨晚闲的无聊,误打误撞碰进去Ubuntu的中国站,感叹于跟当年完全不一样了,12.04以前感觉好难用,现在感觉有点开始高大上起来,于是马上Down了一个iso回来,仔细做个笔记: 1、从官网上下载了Ubuntu16.04的安装镜像,用UltraISO烧进U盘里,U盘最好不少于8G吧,用着安心,教程网上一搜一堆,这里就不缀述了。 2、我电脑上插了2块硬盘,1块500G,用于Win7(前面的文章里说过了),1块1T,刚好用来做Ubuntu,既然地方大,就无所谓分区了。注意你自己装的话,我是强烈不建议在一块硬盘上做2个系统,非常容易把你的数据弄坏。当然,如果不给机箱里再添个硬盘的话,最好把其他地方的重要数据提前备份好。 3、安装的过程比较顺,就是时间稍稍有些长,而且进度条迟迟不走,这时候千万不能着急。按照提示一步一步地做,这里注意:   (1)第一次接触Ubuntu的千万别慌,尤其是在硬盘分区的地方

  • hdu6078[优化递推过程] 2017多校4

    这道题一眼看过去好像和最长公共子序列有点像。 一开始只想到暴力的推法, 令dp[i][j][k]表示a[i]=b[j](即以ai,bj为结尾的波浪序列的方案数),且最终状态为k(0,1分别代表下降与上升)的方案数。    所以我们可能需要优化一下,用一个sum[i][j][k]表示枚举到ai时,能构成以bj为结尾且末状态为k的方案和,可以减少对j这一维的枚举。 比如我们在枚举ai+1时,在遍历b中元素时,如果遇到比ai+1大的,那么就加上sum[i][j][1],若遇到比ai+1小的,就加上sum[i][j][0],如果等于,就更新答案,把前面所有的可能全部加起来,并更新dp[i+1][j][k]。 /*hdu6078[优化递推过程]2017多校4*/ #include<bits/stdc++.h> usingnamespacestd; typedeflonglongLL; constLLMOD=998244353LL; intT,m,n,a[2005],b[2005]; LLsum[2005][3],dp[2005][3];//改为滚动数组,优化空间

相关推荐

推荐阅读