Siyuan's Blog
  • 动态日历

    Loading...

    分类雷达图

    Loading...

    发布统计图

    Loading...

    分类统计图

    Loading...

    标签统计图

    Loading...

  • 闲言碎语
    闲言碎语
    NOIP 2020 Bless All.
    2020-12-4 13:59:42
    Fate in life.
    2020-12-3 15:10:20
    该评论仅登录用户及评论双方可见
    2020-10-24 00:00:00
Siyuan OIer.
  • 晚上好,注意早点休息

  • 导航
  • 首页
  • 归档
  • 友链
  • 组成
  • 分类
    • 分类
    • 题解
      • 5LOJ
      • 1UOJ
      • 7Codeforces
      • 2AtCoder
      • 0BZOJ
      • 0洛谷
      • 1HDU
      • 0POJ
      • 0牛客
      • 051Nod
      • 1TopCoder
      • 0USACO
      • 0CodeChef
      • 0XJOI
    • 47算法
    • 2语法
    • 1游记
    • 3杂类
  • 页面
    • 页面
    • 时光机
    • 归档
    • 友链
  • 友链
    • 友链
管理
文章
评论

标签 区间 DP 下的文章

  1. 首页
  2. 区间 DP

「Codeforces 1178F2」Long Colorful Strip

题目链接:Codeforces 1178F2

世界上有 $n +1$ 种不同的颜色,从 $0$ 到 $n$ 标号。现在你有一张长度为 $m$ 的纸,所有位置的初始颜色均为 $0$。

Alice 通过如下步骤队这张纸染色。她按顺序使用颜色 $1$ 到 $n$ 染色,对于第 $i$ 种颜色,她选择两个整数 $1 \le a_i \le b_i \le m$ 满足位置 $[a_i, b_i]$ 的颜色相同,然后把区间 $[a_i, b_i]$ 都染成颜色 $i$。

通过所有操作,Alice 需要把第 $i$ 个位置染成颜色 $c_i$,你需要求出满足条件的序列对 $\{a_i\}_{i = 1} ^ {n}, \{b_i\}_{i = 1} ^ {n}$ 的数量,答案对 $998244353$ 取模。

数据范围:$1 \le n \le 500$,$n \le m \le 10 ^ 6$,$1 \le c_i \le n$,$\forall 1 \le j \le n, \exists k, c_k = j$。

  • Siyuan
  • 2019 年 07 月 22 日
  • 2 条评论
    • 热门文章
    • 最新评论
    • 随机文章
    热门文章
    • ZJOI 2019 游记

      浏览次数: 11011
    • [数据删除] 2021 算法模板复习!

      浏览次数: 5872
    • 「Codeforces 1228 E」Another Filling the Grid

      浏览次数: 2368
    • 「TJOI 2019」唱、跳、rap 和篮球

      浏览次数: 2309
    • 「算法笔记」多项式模板

      浏览次数: 2128
    最新评论
    • hydingsy
      我是 Siyuan,我 AK IOI
    • hydingsy
      qaq
    • Siyuan.
      Orz
    • Orz Siyuan
      Orz!!!!
    • Orz Siyuan
      Orz Siyuan
    随机文章
    • 「十二省联考 2019」异或粽子

      浏览次数: 408
    • 「算法笔记」泰勒公式和牛顿迭代法

      浏览次数: 646
    • 「算法笔记」二分图多重匹配

      浏览次数: 466
    • 「Codeforces 1073G」Yet Another LCP Problem

      浏览次数: 478
    • 「ARC 103D」Distance Sums

      浏览次数: 404
    博客信息
    • 200文章数目
    • 322评论数目
    • 1年321天运行天数
    • 3 星期前最后活动
    标签云
    数据结构 动态规划 数论 图论 贪心 字符串 多项式 FFT 计数 网络流 LCT 后缀数组 线段树 构造 组合数学 树状数组 CDQ 分治 容斥 并查集 主席树 高斯消元 莫比乌斯反演 最大流 费用流 离线 二分答案 权值线段树 数论分块 生成函数 计算几何 矩阵 最小割 分块 随机化 斜率优化 概率期望 后缀自动机 位运算 莫队 线性基 凸包 平衡树 线性筛 单调栈 杜教筛 行列式 欧拉函数 树形 DP 双指针 模拟退火 整体二分 积性函数 RMQ 决策单调性 FWT 二分 数学归纳法 最小圆覆盖 BSGS 可持久化 拉格朗日插值 同余 exGCD 中国剩余定理 扩展中国剩余定理 最短路 类欧几里德算法 最大子段和 矩阵快速幂 递推 缩点 单调队列 重心 上下界网络流 倍增 二分图 启发式合并 Trie Tarjan 线段树合并 交互 暴力 欧拉路径 斯特林数 Prufer 序列 置换 欧拉定理 Kruskal 重构树 生成树 矩阵树定理 树套树 LCA Kruskal 四边形不等式 点分治 拓扑排序 匈牙利算法 扫描线 长链剖分 AC 自动机 KMP 牛顿迭代法 泰勒公式 背包 区间 DP 鸽巢原理 树链剖分 笛卡尔树 欧拉公式 数学
    Powered by Typecho | Theme by handsome © 2021 Copyright 浙ICP备19008446号-1