首页 > 其他分享 >CF848E Days of Floral Colours 题解

CF848E Days of Floral Colours 题解

时间：2025-01-01 21:09:07浏览次数：5  
标签：CF848E 题解 2x len int Floral MOD 配对 define

Problem - 848E - Codeforces

首先，由于整个图是对称的，所以我们将其沿直径分为两半，在算一半答案时把每一段的贡献平方再相加即可。（因为对面也有一段相同长度的也要计入贡献）

现在我们的问题转化为了对于一个长为 \(n\) 的环，你可以给一个点连出一个线头（即在原图中连向对面的边）将其余点进行配对，每一对的距离不能超过 \(2\)。求总权值和。

对于环上问题，我们先破环为链，我们若随机指定一个点作为破开的起点则可能出现一段甚至一个配对横跨首尾的情况，不可取。我们选择指定一个线头，枚举线头向后一段的长度，最终再乘上这个贡献即可。

现在我们需要考虑一个序列问题：对于每个 \(n\) ，求一个长为 \(n\) 的序列，在上面留线头或者配对的总权值和。

由于要求出每个 \(n\) 的答案，考虑 DP。

为了方便计算，我们先不管线头，先算出来一个长为 \(n\) 的配对方案数，记为 \(x_n\)。

对于一个状态，我们可以向后放一个长度为 \(1\) 的配对或者两个长度为 \(2\) 的配对交叉起来，所以：

\[x_n=x_{n-2}+x_{n-4} \]

好了，现在进入本题的核心。

我们发现我们上面所考虑的序列问题是不严谨的。

因为可能左侧和右侧会伸出去一个长度为 \(2\) 的配对，这一点在破环为链中很重要，因为计算答案的系数不同。

所以我们现在需要计算一个序列向左右都不伸出去配对，向左伸出 \(1\) 个配对和左右都伸出配对的权值和。（向左和向右对称）

我们分别记他们为 \(f_n,g_n,h_n\)。

接下来开始暴力推式子环节，推式子的过程本身小学生都可以完成，这里不放一坨坨 \(\LaTeX\) 了。

结论：

\[f_n=(n-1)^2x_{n-1}+\sum_{i=1}^{n-1}f_{n-i}(i-1)^2x_{i-1}+\sum_{i=2}^{n-2}g_{n-i}(i-1)^2x_{i-2} \]

\[g_n=(n-1)^2x_{n-2}+\sum_{i=2}^{n-1}f_{n-i}(i-1)^2x_{i-2}+\sum_{i=3}^{n-2}g_{n-i}(i-1)^2x_{i-3} \]

\[h_n=(n-1)^2x_{n-3}+\sum_{i=2}^{n-2}g_{n-i}(i-1)^2x_{i-2}+\sum_{i=3}^{n-3}h_{n-i}(i-1)^2x_{i-3} \]

很好，现在我们已经做完了。

我们发现这个式子直接进行递推是 \(\Theta(n^2)\) 的，显然无法通过此题。

但是我们注意到对于每个 \(i\) 的系数在对应的方程位置里是固定的。

我们使用分治 FFT 进行计算即可。

实现细节：

可以设立一个 update 函数进行计算一个式子对后面的贡献，利用另外三个数组来表示转移方程中的系数，即可优雅地实现这个原本代码实现难度相当高的题目。

详细看代码。

/*
 * @Author: LightningCreeper l_ghtn_ngcr__p_r@outlook.com
 * @Date: 2024-12-30 21:01:12
 * @LastEditors: LightningCreeper l_ghtn_ngcr__p_r@outlook.com
 * @LastEditTime: 2024-12-30 21:46:22
 * @FilePath: /i.省队训练/C.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <bits/stdc++.h>
#pragma GCC optimize(3, 2, 1, "Ofast")
using namespace std;

#define int long long
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define gn(u, v) for (int v : G.G[u])
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tomin(x, y) ((x) = min((x), (y)))
#define tomax(x, y) ((x) = max((x), (y)))
#define ck(mask, i) (((mask) >> (i)) & 1)
#define pq priority_queue
#define FLG (cerr << "Alive!" << endl);

constexpr int MAXN = 2e5 + 5;

constexpr int MOD = 998244353;
constexpr int G = 3;
constexpr int GINV = 332748118;

int qpow(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}

int rt[MAXN];

void NTT(int x[], int len, bool t) {
    for (int i = 0; i < len; i++)
        if (i < rt[i])
            swap(x[i], x[rt[i]]);
    for (int i = 1; i < len; i *= 2) {
        int n;
        if (t)
            n = G;
        else
            n = GINV;
        n = qpow(n, (MOD - 1) / (i * 2));

        for (int j = 0; j < len; j += (i * 2)) {
            for (int k = 0, t = 1; k < i; k++, t = (t * n) % MOD) {
                int p = x[j + k];
                int q = t * x[j + k + i] % MOD;
                x[j + k] = (p + q);
                x[j + k + i] = p - q + MOD;
                if (x[j + k] >= MOD)
                    x[j + k] -= MOD;
                if (x[j + k + i] >= MOD)
                    x[j + k + i] -= MOD;
            }
        }
    }
}

void Times(int a[], int b[], int len) {
    int l = __lg(len);
    for (int i = 0; i < len; i++)
        rt[i] = 0;
    for (int i = 0; i < len; i++)
        rt[i] = (rt[i >> 1] >> 1) | ((i & 1) << (l - 1));

    NTT(a, len, true);
    NTT(b, len, true);
    for (int i = 0; i < len; i++)
        a[i] = a[i] * b[i] % MOD;
    NTT(a, len, false);
    NTT(b, len, false);
    int inv = qpow(len, MOD - 2);

    for (int i = 0; i < len; i++) {
        a[i] = a[i] * inv % MOD;
        b[i] = b[i] * inv % MOD;
    }
}

int n;
int tmp[MAXN], f0[MAXN], g0[MAXN], f1[MAXN], g1[MAXN], f2[MAXN], g2[MAXN], g[MAXN];

void update(int f[], int g[], int h[], int len) { // f = gh, h on the left
    for (int i = 0; i < len * 2; i++)
        tmp[i] = 0;
    for (int i = 0; i < len / 2; i++)
        tmp[i] = h[i];
    Times(tmp, g, len * 2);

    for (int i = len / 2; i < len; i++)
        (f[i] += tmp[i]) %= MOD;
}

void CDQ(int l, int r) {
    if (l + 1 == r) {
        (f0[l] += g0[l]) %= MOD;
        (f1[l] += g1[l]) %= MOD;
        (f2[l] += g2[l]) %= MOD;
        return;
    }

    int mid = l + r >> 1;
    int len = r - l;
    CDQ(l, mid);

    update(f0 + l, g0, f0 + l, len);
    update(f0 + l, g1, f1 + l, len);
    update(f1 + l, g1, f0 + l, len);
    update(f1 + l, g2, f1 + l, len);
    update(f2 + l, g1, f1 + l, len);
    update(f2 + l, g2, f2 + l, len);

    CDQ(mid, r);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    g[0] = g[2] = 1;
	for (int i = 4; i <= n; ++i)
        g[i] = (g[i - 2] + g[i - 4]) % MOD;
	for (int i = 1; i <= n; ++i)
        g0[i] = (i - 1) * (i - 1) * g[i - 1] % MOD;
	for (int i = 2; i <= n; ++i)
        g1[i] = (i - 1) * (i - 1) * g[i - 2] % MOD;
	for (int i = 3; i <= n; ++i)
        g2[i] = (i - 1) * (i - 1) * g[i - 3] % MOD;
    
    int len = (1 << (__lg(n) + 1));
    CDQ(0, len);
    // FLG
    int ans = n * (g0[n] + g2[n]) % MOD;
    for (int i = 2; i < n - 1; i++)
        (ans += i * (g0[i] * f0[n - i] % MOD + 2 * g1[i] * f1[n - i] % MOD + g2[i] * f2[n - i] % MOD) % MOD) %= MOD;
    cout << ans << endl;

    return 0;
}

经验总结：
对于一类看起来很唬人的计数题，先做出一个多项式做法的 DP，再考虑优化，且在转移方程中出现在固定位置系数不变的情况可以使用分治 FFT 优化。以及，在分治 FFT 中将多个求和放在一起算可大大提升常数。

标签：CF848E,题解,2x,len,int,Floral,MOD,配对,define
From： https://www.cnblogs.com/LightningCreeper/p/18646298

相关文章

  • Luogu P9646 SNCPC2019 Paper-cutting 题解 [ 紫 ] [ manacher ] [ 贪心 ] [ 哈希 ] [
    Paper-cutting：思维很好，但代码很构式的manacher题。蒟蒻2025年切的第一道题，是个紫，并且基本独立想出的，特此纪念。判断能否折叠我们先考虑一部分能折叠需要满足什么条件。显然，这一部分需要是一个长度为偶数的回文串。那么横向和纵向会不会影响呢？答案是不会，因为横向折了之后，折......
  • CF601E A Museum Robbery 题解
    题目传送门前置知识线段树与离线询问解法普通的回退背包无法处理本题中的删除操作，考虑线段树分治后转化为只进行添加的背包。具体实现时可以对每个深度开一个背包的转移数组，时间复杂度为\(O(nk\logq+qk)\)，可以接受。代码#include<bits/stdc++.h>usingnamespacestd;#......
  • 洛谷 P11487 「Cfz Round 5」Gnirts 10——题解
    洛谷P11487「CfzRound5」Gnirts10传送锚点摸鱼环节「CfzRound5」Gnirts10题目背景Englishstatement.YoumustsubmityourcodeattheChineseversionofthestatement.InMemoryof\(\text{F}\rule{66.8px}{6.8px}\).题目描述题面还是简单一点好。给定......
  • 题解：AT_abc386_d [ABC386D] Diagonal Separation
    分析题面，发现题目求的是是否存在一个白点被\((1,1)\)和任意一个黑点围成的矩形内。先将所有黑点按\(x\)坐标排序。枚举所有的白点。找到所有横坐标不比该白点横坐标小的所有黑点的纵坐标的最大值所属点。如果该点的纵坐标小于该白点的纵坐标：（蓝点代表题目中的白点，红点......
  • 百丽宫24年春季真题题解——回型字符的打印
    不妨参考之前的一道选做题思路（虽然楼主自己之前也没找到时间做）但当时瞟过一眼题目，个人认为可以一起做，都是你中有我的关系，思路很相似。选做题摘录——晕：看着这样的"回”形图案你晕吗？让我们不用数组，来做出它。输入格式：n。正方形的边长输出格式："%3d"   边长为n的数字回......
  • 百丽宫22年真题题解——最短路径（排列组合法）
    #include<stdio.h>unsignedlonglonghigh;unsignedlonglonglow;unsignedlonglongfac(intn,intm){unsignedlonglongi,f=1;if(m!=1){for(i=n;i>=n-m+1;i--){f=f*i;}returnf;}elseif(m......
  • 自动推理与规划：让机器具备智能决策与问题解决能力
    随着人工智能技术的不断进步，自动推理与规划（AutomatedReasoningandPlanning）已经成为使机器具备高效决策和问题解决能力的核心技术之一。它涉及如何通过逻辑推理、任务规划和约束求解，使机器能够自主地解决复杂问题、制定行动策略，并在不断变化的环境中做出最优决策。自动推理......
  • 题解：CF727F Polycarp's problems
    link。贪心做法。本题贪心做法的实质就是用整数尽量多地抵消该整数后面的负数。如果正着做，没有办法考虑全该数后面的所有负数，所以倒着做。例如当前遍历到了\(50\)，此时序列如下：\[\dots,50,-50,-10,-20\]易得我们\(50\)应该抵消的是\(-10,-20\)，而不是前面的\(-50\)，因为......
  • Web 前端面试指南与高频考题解析
    Web前端面试指南与高频考题解析准备：简历编写和面试前准备一般来说，跳槽找工作要经历投递简历、准备面试、面试和谈offer四个阶段。其中面试题目会因你的等级和职位而异，从入门级到专家级，广度和深度都会有所增加。不过，不管什么级别和职位，面试题目一般都可以分类为理论知识、算法......
  • 2024 idea安装教程以及常见的问题解答（附激活至2026 实际永久 亲测）
    2024idea安装激活使用教程以及常见的问题解答，例如会反复跳出激活码并提示无效，显示Keyisinvalid或者打不开等下载IDEA安装包也可以在这里点击下载idea（含博主使用版本）下载idea安装IDEA点击xx关掉程序！下载补丁IntelliJIDEA补丁文件点击获取补丁下载成功后，打开......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99