首页 > 其他分享 >题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】

题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】

时间：2023-10-16 23:02:04浏览次数：41  
标签：P7468 const NOI int 题解 sum return modint size

题解 P7468【[NOI Online 2021 提高组] 愤怒的小 N】

problem

首先是有一个字符串 \(S=\texttt{"0"}\)，做无限次“将 \(S\) 的每一位取反接在 \(S\) 后面”的操作，形如 \(S=0110100110010110\cdots\)。

另外给一个 \(k-1\) 次多项式 \(f\)，求 \(\sum_{i=0}^{n-1}S_if(i).\)

\(n\leq 2^{5\times 10^5}, k\leq 500\)。

solution 0

第一个观察是 \(S_i=parity(i)\)。因为每次将高位拿掉，值就反转。

考虑 dp。\(dp(i, j, 0/1)\) 表示 \([0,2^i)\) 中 \(parity=0/1\) 的数字的 \(j\) 次方和。

转移

初值为 \(dp(0, j, 0)=[j=0]\) 表示只有 \(0\) 一个数字。

\[\begin{aligned} dp(i, j, e)&=dp(i-1, j, e)+\sum_{l=0, parity(l)\neq e}^{2^{i-1}-1}(l+2^{i-1})^j\\ &=dp(i-1, j, e)+\sum_{l=0, parity(l)\neq e}^{2^{i-1}-1}\sum_{t=0}^{j}\binom{t}{j}l^t(2^{i-1})^{j-t}\\ &=dp(i-1, j, e)+\sum_{t=0}^{j}\binom{j}{t}(2^{i-1})^{j-t}\sum_{l=0, parity(l)\neq e}^{2^{i-1}-1}l^t\\ &=dp(i-1, j, e)+\sum_{t=0}^{j}\binom{j}{t}(2^{i-1})^{j-t}dp(i-1, t, e\oplus 1)\\ \end{aligned} \]

统计答案

  • 取出 \(2^T=lowbit(n), L=n-2^T\)。

  • 答案累加 \(\displaystyle\sum_{l=L, parity(l)\neq parity(L)}^{L+2^t-1}f(l)\)。注意这里 \(l-L, L\) 相加不进位，所以这玩意等于

  • \[\begin{aligned} \displaystyle\sum_{l=L, parity(l)\neq parity(L)}^{L+2^T-1}\sum_{j=0}^{k-1}f_j(l+L)^j &=\displaystyle\sum_{l=L, parity(l)\neq parity(L)}^{L+2^T-1}\sum_{j=0}^{k-1}\sum_{t=0}^{j}\binom{j}{t} f_jl^tL^{j-t}\\ &=\sum_{j=0}^{k-1}\sum_{t=0}^{j}\binom{j}{t} f_jL^{j-t}\displaystyle\sum_{l=L, parity(l)\neq parity(L)}^{L+2^T-1}l^t\\ &=\sum_{j=0}^{k-1}\sum_{t=0}^{j}\binom{j}{t} f_jL^{j-t}dp(T, t, parity(L)\oplus 1)\\ &=\sum_{t=0}^{k-1}dp(T, t, parity(L)\oplus 1)\sum_{j=t}^{k-1}\binom{j}{t} f_jL^{j-t}\\ \end{aligned} \]

  • \(n:=L\)。

  • 明显枚举了所有区间。

optimize

现在的复杂度是 \(O(k^2\log n)\)。

重量级结论是，\(i>j\) 时 \(dp(i, j, 0)=dp(i, j, 1)=\frac{1}{2}\sum_{l=0}^{2^i-1}l^j\)。（怎么证明呢，待补，关键是对 \(i-1\to i\) 归纳，用二项式定理展开，考察各项系数）

换句话来说，对于 \(i>j\) 的一大段区间，我们直接求出整段区间的 \(f\) 的和，然后除以二就断定是区间的答案。这一大段区间，只算 \(i\geq k,j<k\) 的，就是 \(0\) 到 “\(n\) 的二进制表示中后面 \(k\) 为改成 \(0\)” 减一，于是可以计算。并观察到 \(f\) 的前缀和是 \(k-1\) 次多项式，考虑直接拉格朗日插值，\(O(k^2)-O(n+k)\) 完成这一部分。

可能发生 \(i<j\) 的区间，假定是 \(i<k\) 的，暴力计算是 \(O(k^3)\) 的。

所以总的复杂度是 \(O(\log n+k^3)\)。就是将其中一个很大的 \(\log n\) 用结论打成 \(k\)。

code


#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <unsigned P>
struct modint {
    unsigned v;
    modint() : v(0) {}
    template <class T>
    modint(T x) { x %= (int)P, v = x < 0 ? x + P : x; }
    modint operator+() const { return *this; }
    modint operator-() const { return modint(0) - *this; }
    modint inv() const { return assert(v), qpow(*this, P - 2); }
    friend int raw(const modint &self) { return self.v; }
    template <class T> friend modint qpow(modint a, T b) {
        modint r = 1;
        for (; b; b >>= 1, a *= a) if (b & 1) r *= a;
        return r;
    }
    modint &operator+=(const modint &rhs) { if (v += rhs.v, v >= P) v -= P; return *this; }
    modint &operator-=(const modint &rhs) { if (v -= rhs.v, v >= P) v += P; return *this; }
    modint &operator*=(const modint &rhs) { v = 1ull * v * rhs.v % P; return *this; }
    modint &operator/=(const modint &rhs) { return *this *= rhs.inv(); }
    friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
    friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
    friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
    friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
    friend bool operator==(const modint &lhs, const modint &rhs) { return lhs.v == rhs.v; }
    friend bool operator!=(const modint &lhs, const modint &rhs) { return lhs.v != rhs.v; }
};
typedef modint<1000000007> mint;
vector<mint> multiple(const vector<mint> &a, const vector<mint> &b) {
    vector<mint> c(a.size() + b.size() - 1);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) c[i + j] += a[i] * b[j];
    }
    return c;
}
vector<mint> addition(const vector<mint> &a, const vector<mint> &b) {
    vector<mint> c(max(a.size(), b.size()));
    for (int i = 0; i < a.size(); i++) c[i] += a[i];
    for (int i = 0; i < b.size(); i++) c[i] += b[i];
    return c;
}
vector<mint> divide(vector<mint> a, mint b1) {
    vector<mint> res(a.size() - 1);
    for (int i = (int) a.size() - 1; i >= 1; i--) {
        mint coe = res[i - 1] = a[i];
        a[i - 1] -= a[i] * b1;
    }
    return res;
}
vector<mint> numes[510];
mint idenos[510];
vector<mint> lagrange(const vector<mint> &a, const vector<mint> &b) {
    assert(a.size() == b.size());
    vector<mint> ans(a.size());
    for (int i = 0; i < a.size(); i++) {
        mint coe = b[i];
        for (int j = 0; j < a.size(); j++) ans[j] += numes[i][j] * coe;
    }
    return ans;
}
mint getValue(const vector<mint> &a, mint x) {
    mint res = 0;
    for (int i = (int) a.size() - 1; i >= 0; i--)
        res = res * x + a[i];
    return res;
}
int n, k;
char a[1 << 19];
vector<mint> f, sumG[510], sumF; //sumG[j](n) = sum{i=0..n-1} i^j
mint dp[510][510][2], qp2[1 << 19], binom[510][510];
const mint inv2 = 1 / mint(2);
void init() {
    for (int i = raw(qp2[0] = 1); i <= max(k * k, n); i++) qp2[i] = qp2[i - 1] + qp2[i - 1];
    for (int i = 0; i < k; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
    }
    vector<mint> per = {};
    for (int i = 1; i <= k + 1; i++) per.push_back(i);
    vector<mint> ans(per.size()), product = {1};
    for (int i = 0; i < per.size(); i++) 
        product = multiple(product, {-per[i], 1});
    for (int i = 0; i < per.size(); i++) {
        numes[i] = divide(product, -per[i]);
        idenos[i] = 1;
        for (int j = 0; j < per.size(); j++)
            if (i != j) idenos[i] *= per[i] - per[j];
        idenos[i] = 1 / idenos[i];
        for (int j = 0; j < per.size(); j++) numes[i][j] *= idenos[i];
    }
    for (int j = 0; j < k; j++) {//这一段没用，，，
        vector<mint> tmp = {};
        for (int i = 1; i <= k + 1; i++) tmp.push_back(qpow(mint(i - 1), j));
        for (int i = 1; i <= k; i++) tmp[i] += tmp[i - 1];
        sumG[j] = lagrange(per, tmp);
    }
    { 
        vector<mint> tmp = {};
        for (int i = 1; i <= k + 1; i++) tmp.push_back(getValue(f, i - 1));
        for (int i = 1; i <= k; i++) tmp[i] += tmp[i - 1];
        sumF = lagrange(per, tmp);
    }
}
void DP() {
    for (int j = 0; j < k; j++) dp[0][j][0] = !j;
    for (int i = 1; i < min(n, k); i++) {
    //for (int i = 1; i < n; i++) {
        memcpy(dp[i], dp[i - 1], sizeof dp[i]);
        for (int j = 0; j < k; j++) {
            for (int e: {0, 1}) {
                for (int t = 0; t <= j; t++) {
                    dp[i][j][e] += dp[i - 1][t][1 - e] * binom[j][t] * qp2[(i - 1) * (j - t)];
                }
            }
        }
    }
    //forall i > j, dp[i][j][e] = sumg[j](2^i) / 2
}
mint solve() {
    mint L = 0, ans = 0;
    bool flag = 0;
    if (n > k) {
        mint lim = 0;
        for (int i = n - 1; i >= k; i--) if (a[i]) lim += qp2[i];
        ans += getValue(sumF, lim) * inv2;
        for (int i = n - 1; i >= k; i--) if (a[i]) {
            L += qp2[i], flag ^= 1;
        }
    }
    for (int i = min(k, n) - 1; i >= 0; i--) if (a[i]) {
        for (int t = 0; t < k; t++) {
            mint coe = 0, now = 1;
            for (int j = t; j < k; j++, now *= L) 
                coe += binom[j][t] * f[j] * now;
            ans += dp[i][t][flag ^ 1] * coe;
        }
        L += qp2[i], flag ^= 1;
    }
    return ans;
}
int main() {
    scanf("%s%d", a, &k), n = strlen(a);
    for (int i = 0; i < n; i++) a[i] -= '0';
    reverse(a, a + n);
    f = vector<mint>(k);
    for (int i = 0; i < k; i++) scanf("%u", &f[i].v);
    init(), DP();
    printf("%d\n", raw(solve()));
    return 0;
}

标签：P7468,const,NOI,int,题解,sum,return,modint,size
From： https://www.cnblogs.com/caijianhong/p/solution-P7468.html

相关文章

  • 题解 ABC267F【Exactly K Steps】
    (accoders::NOI#5541.醉(intoxicated)）题目描述Robin有一棵树，他有\(m\)次询问，每次询问他给你\(u,k\)，你需要输出树上的一个节点\(v\)满足\(dist(u,v)=k\)，或者报告无解。\(dist(u,v)\)表示树上\(u\)到\(v\)的最短路径的边数。\(n\leq10^5\)solution考虑求出每个......
  • Math teacher's homework 题解
    preface网上的题解看不懂，看代码看懂了：）solution考虑\(\mathrm{x_i}\)的倒数第\(\mathrm{low_i-1}\)位到倒数第\(\mathrm{1}\)位可以乱选（选\(\mathrm{0/1}\)都满足\(\mathrm{x_i\leqm_i}\)），那么就需要\(\mathrm{x_i}\)和\(\mathrm{m_i}\)的第\(\mathrm{1}\)位......
  • YACS 2023年9月月赛 甲组 题解
    题目链接1题目链接2题目链接3榜单终于公布了，这应该是第二长的榜单公布吧。（最长的一次是去年八月，拖到九月开始后才公布） T1是傻逼数据结构不说了吧，对于每个点枚举以他为角的$k\timesk$的四个正方形算一下点的数量，用$cdq$或者扫描线都行。看这个题目编号是$81$，看来是很......
  • 题解整理
    CF1740ACF1740BCF1740DCF1711BCF1253BCF1080BCF1237ACF1743ACF1743CCF1743BCF1370B......
  • P9744 消除序列 题解
    本题有多种解法，我这里先讲一个我的考场做法吧。切入点我们发现我们至多使用一次操作一，而剩下部分的\(0\)肯定是依靠操作二补全，操作三的作用只是用来填补操作一的空白的，所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三，后一段用操作二。思路1一开始考虑暴力\(......
  • CEIT 23练习编程题 题解
    本文部分题目提供c/c++两种解法,顺便可以让你们知道c++在面对某些题时的优势部分题目提供多种解法日期格式化C#include<stdio.h>intmain(){intm,d,y;scanf("%d-%d-%d",&m,&d,&y);printf("%04d-%02d-%02d",y,m,d);return0;}02d的含义:当有效数......
  • 【题解】「KDOI-06-S」补题
    「KDOI-06-S」A.「KDOI-06-S」消除序列赛时写了一个\(O(nq)\)的线性DP，喜提60分。注意到如果操作1被使用，则一定只会使用一次，而且在最优策略中一定是第一次使用操作1。则我们可以通过以下方式进行操作，使序列满足条件：首先执行\(a_i\)和\(\sum^{j\lei,i\inP}_{j=......
  • [COCI2015-2016#4] ENDOR 题解
    [COCI2015-2016#4]ENDOR题解首先要发现一个很重要的性质，那就是两只变色龙碰撞后回头，等效于两只变色龙继续往前走，其中向右走的颜色不变，而向左走的要改变颜色。那这样就有一种\(O(n^2)\)的做法：对于向右的变色龙，直接贡献答案；对于向左的变色龙，我们按照碰到的先后顺序枚举它前面......
  • 【题解】AtCoder-ARC167
    AtCoder-ARC167AToastsforBreakfastParty一定不会有空盘，问题转化成\(2m\)个数，其中\(2m-n\)个是\(0\)，这样一定是最大值和最小值一起，次大值和次小值一起，以此类推。提交记录：Submission-AtCoderAtCoder-ARC167BProductofDivisors\(A^B=\prod_ip_i^{Bc_i}\)，那么答案......
  • CF1119F Niyaz and Small Degrees 题解
    原题翻译首先\(O(n^2\logn)\)的dp是simple的，我们设\(dp_{i,0/1}\)表示以\(i\)为根，\(i\)到\(fa_i\)这条边删/不删的最小权值和。转移是一个非常trick的问题，只需要假设所有都选\(dp_{i,0}\)，然后把所有儿子按照\(dp_{v,1}+w(u,v)-dp_{v,0}\)排序，选前\(d......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99