当前位置: 首页 > news >正文

NOI 模拟赛五

A.

纪念场切题。

\(f[i, j, x, 0/1, 0/1]\) 表示前 \(i\) 个车站都已经经过,\(i\rightarrow i+1\) 的边走过 \(j\) 次,总距离 \(\bmod m=x\) ,是否钦定起点,是否钦定终点(这 \(j\) 条边经过是有顺序)。

为了转移简便,我们强制起点在终点之前钦定,最后将答案全部 \(\times 2\) 即可,因为过程是完全对称的。

以已钦定起点,未钦定终点为例(注意到 \(j\) 一定为奇数)。

  • 钦定 \(i\) 为终点
    • \(j\) 中的最后一条停留在这里,转移到 \(f[i, j-1, nx, 1, 1]\)
    • \(j\) 全部顺延,最后再返回一条边终止于 \(i\) ,转移到 \(f[i, j+1, nx, 1, 1]\)
  • \(i\) 不为终点
    • \(j\) 中的某条边“顺路”经过 \(i\)\(\times j\rightarrow f[i, j, nx, 1, 0]\)
    • \(j\) 中的某组边(向右又向左)经过 \(i\) ,这样的组有 \(\frac{j-1}{2}\) 个,\(\times \frac{j-1}{2}\rightarrow f[i, j-2, nx, 1, 0]\)
    • \(j\) 全部顺延,最后返回一组边经过 \(i\) , 这样的位置有 \(\frac{j+1}{2}\) 个,\(\times \frac{j+1}{2}\rightarrow f[i, j+2, nx, 1, 0]\)

上文中, \(nx=(x+j\times \Delta x)\bmod m\)

初值直接赋给 \(1\) 是/不是起点就好了,直接赋值 \(2\) 省去 \(\times 2\) 的过程。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 1000 + 7;
const int LM = 100 + 7;
const int mod = 998244853;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int T, n, m, a[LN], f[2][LN][LM][2][2];bool ENDPOS;il int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
il void upa(int& u, int v) { u = add(u, v); }
il int mul(ll u, ll v) { return u * v >= mod ? u * v % mod : u * v; }
il void upm(int& u, int v) { u = mul(u, v); }int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock(), nx;std::cin >> T;while (T--) {std::cin >> n >> m;lep(i, 1, n) std::cin >> a[i];std::sort(a + 1, a + 1 + n);lep(i, 1, n) a[i] %= m;int p = 0;std::memset(f[p], 0, sizeof(f[p]));f[p][1][0][1][0] = f[p][2][0][0][0] = 2;lep(i, 2, n) {std::memset(f[p ^ 1], 0, sizeof(f[p ^ 1]));lep(j, 1, n) lep(x, 0, m - 1) { nx = (1ll * (m + a[i] - a[i - 1]) * j % m + x) % m;if (j & 1) {//S nupa(f[p ^ 1][j - 1][nx][1][1], f[p][j][x][1][0]);upa(f[p ^ 1][j + 1][nx][1][1], f[p][j][x][1][0]);upa(f[p ^ 1][j][nx][1][0], mul(j, f[p][j][x][1][0]));if (j >= 2) upa(f[p ^ 1][j - 2][nx][1][0], mul(j / 2, f[p][j][x][1][0]));upa(f[p ^ 1][j + 2][nx][1][0], mul(j / 2 + 1, f[p][j][x][1][0]));}else {// S Tupa(f[p ^ 1][j][nx][1][1], mul(j, f[p][j][x][1][1]));if (j >= 2) upa(f[p ^ 1][j - 2][nx][1][1], mul(j / 2, f[p][j][x][1][1]));upa(f[p ^ 1][j + 2][nx][1][1], mul(j / 2, f[p][j][x][1][1]));//n nupa(f[p ^ 1][j][nx][0][0], mul(j, f[p][j][x][0][0]));if (j >= 2) upa(f[p ^ 1][j - 2][nx][0][0], mul(j / 2 - 1, f[p][j][x][0][0]));upa(f[p ^ 1][j + 2][nx][0][0], mul(j / 2 + 1, f[p][j][x][0][0]));if (j) upa(f[p ^ 1][j - 1][nx][1][0], f[p][j][x][0][0]);upa(f[p ^ 1][j + 1][nx][1][0], f[p][j][x][0][0]);}}p ^= 1;}lep(i, 0, m - 1) std::cout << f[p][0][i][1][1] << ' ';std::cout << '\n';}#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

http://www.hskmm.com/?act=detail&tid=17347

相关文章:

  • 什么是Delphi4Python?
  • 实用指南:Python的大杀器:Jupyter Notebook处理.ipynb文件
  • flask认证机制logging模块实战
  • 25.9.25随笔联考总结
  • 软工9.25
  • 2025/9/25 模拟赛总结
  • 代码随想录算法训练营第九天 |151.翻转字符串里的单词、 LCR 182. 动态口令、28. 实现 strStr()、459.重复的子字符串
  • 当日总结(课后作业2)
  • Codeforces Global Round 29 (Div. 1 + Div. 2) A~E
  • AI 低代码平台:不止于 “快”,解码技术融合的深层逻辑
  • 实用指南:【知识拓展Trip Five】寄存器
  • 计算机视觉(opencv)实战二十七——目标跟踪 - 教程
  • P8367 [LNOI2022] 盒
  • 蓝桥杯 2025 省 B 题:画展布置 - 题解笔记
  • 二维坐标下的运算
  • Polar2025秋季个人挑战赛web-writeup
  • Day4
  • 题解:P12751 [POI 2017 R2] 集装箱 Shipping containers
  • 弱网配置
  • 绘制金融集团监控大屏的地图demo
  • 实用指南:《原神助手》开源神器:游戏体验大升级
  • 9-25
  • AT_agc021_d [AGC021D] Reversed LCS
  • adb shell 常用文件命令
  • Java文件编程
  • 自我介绍与规划
  • 软件工程学习日志2025.9.25
  • 从50ms到30ms:YOLOv10部署中图像预处理的性能优化实践 - 实践
  • redis实现分布式锁1
  • 完整教程:(13)GPS/无GPS转换