首页 > 其他分享 >《如 何 速 通 一 套 题》5.0

《如 何 速 通 一 套 题》5.0

时间:2024-09-23 16:13:12浏览次数:10  
标签:5.0 tmp return pbs int long fib

邮寄

开场直接看 A。A 做不出来。

浏览了一下,发现 A 是 sb 题,直接做了。

BCD 全都不会做。

推了好久的 B,想出来了,然后写过了。

CD 一个暴力,一个乱搞,然后撤退。

A 依依寺

\(a\) 没用,对 \(b\) 和 \(c\) 分类讨论。

死于不开 long long 见祖宗。

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

int t, a, b, c, ans;

int main() {
  //freopen("yiyi.in", "r", stdin);
  //freopen("yiyi.out", "w", stdout);
  for(cin >> t; t--; ) {
    cin >> a >> b >> c;
    ans = 0;
    if((!b) && (!c)) {
      cout << "Second" << '\n';
      continue;
    }
    if(b) {
      b--;
      ans |= (b <= c) ^ (a & 1);
      b++;
    }
    if(c) {
      c--;
      ans |= (c <= b) ^ (a & 1);
      c++;
    }
    cout << (ans? "First" : "Second") << '\n';
  }
  return 0;
}

B 武义寺

考虑每一个 \(\operatorname{val}\) 的可能取值。

对于取值为 \(i\) 的情况,前 \(i - 1\) 个数必须满足 \(j \leq a_j\),第 \(i\) 个数必须满足 \(i > a_i\),其他随便。

先考虑第一个条件。

记 \(pbs_i\) 表示 前 \(i\) 个数满足 \(j \leq a_j\) 的概率,从后往前看,易得 \(pbs_i = \frac{(n - i + 1)^i \times (n - i)!}{n!}\)。

然后考虑第二个条件。可知 \(\operatorname{val}(p) = i\) 的概率是 \(pbs_{i - 1} - pbs_i\)。

然后就可以直接做了。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int kMod = 998244353;

int n, fac[1000010], ivs[1000010], inv[1000010], pbs[1000010], prb[1000010], ans;

int qpow(int x, int y) {
  int rs = 1;
  for(; y; y >>= 1) {
    if(y & 1) {
      rs = rs * x % kMod;
    }
    x = x * x % kMod;
  }
  return rs;
}

int qinv(int x) {
  return qpow(x, kMod - 2);
}

void init() {
  fac[0] = 1;
  for(int i = 1; i <= 1000000; i++) {
    fac[i] = fac[i - 1] * i % kMod;
  }
  ivs[1000000] = qinv(fac[1000000]);
  for(int i = 999999; i >= 0; i--) {
    ivs[i] = ivs[i + 1] * (i + 1) % kMod;
  }
  for(int i = 1; i <= 1000000; i++) {
    inv[i] = ivs[i] * fac[i - 1] % kMod;
  }
}

signed main() {
  //freopen("wuyi.in", "r", stdin);
  //freopen("wuyi.out", "w", stdout);
  init();
  cin >> n;
  pbs[0] = 1;
  for(int i = 1; i <= n; i++) {
    pbs[i] = qpow(n - i + 1, i) * fac[n - i] % kMod * ivs[n] % kMod;
  }
  for(int i = 1; i <= n + 1; i++) {
    prb[i] = (pbs[i - 1] - pbs[i] + kMod) % kMod;
    ans = (ans + i * prb[i]) % kMod;
  }
  cout << ans << '\n';
  return 0;
}

C 依久依久

超级大数学。

区间复杂东西的复杂运算,可差分,果断祭出前缀和。

对于 \(l = 1\),不难想到一位一位处理。

找到 \(n\) 的最高位,设是第 \(k\) 位,对应的数是 \(fib_k\)。我们把这一位的贡献算上,然后递归处理。

写出来就是:

\[\operatorname{S}(n) = \operatorname{S}(fib_k - 1) \ \oplus \ \operatorname{S}(n - fib_k) \ \oplus \ \begin{cases} fib_k &\text{if } n - fib_k + 1 \text{ is odd} \\ 0 &\text{otherwise} \end{cases} \]

// 实际写出来的代码短得神奇
#include <bits/stdc++.h>
#define int long long
using namespace std;

int t, l, r, ans, f[114], n;
map<int, int> mem;

int cal(int x) {
  if(!x) {
    return 0;
  }
  if(mem.find(x) != mem.end()) {
    return mem[x];
  }
  int tmp = upper_bound(f + 1, f + n + 1, x) - f - 1;
  return mem[x] = (cal(f[tmp] - 1) ^ cal(x - f[tmp]) ^ (((x - f[tmp] + 1) & 1) * f[tmp]));
}

signed main() {
  freopen("yijiu.in", "r", stdin);
  freopen("yijiu.out", "w", stdout);
  f[0] = f[1] = 1;
  for(n = 2; (f[n] = f[n - 1] + f[n - 2]) <= (int)(1e18); n++) {
  }
  for(cin >> t; t--; ) {
    cin >> l >> r;
    cout << (cal(r) ^ cal(l - 1)) << '\n';
  }
  return 0;
}

标签:5.0,tmp,return,pbs,int,long,fib
From: https://www.cnblogs.com/leavenothingafterblog/p/18426978/speedrun_v5-0

相关文章

  • 短说社区V5.0测试版来啦! 快来关注最新版本~
    Hi大家好,我是给你们带来惊喜的运营小番茄。本期是一期大家期待已久的重磅更新! 5.0.0测试版来啦!随小番茄一期了解一下本次更新主要有哪些内容吧~ 一、移动端新版UI本次更新除UI全新升级之外,在升级UI的同时我们还做了一些使用体验的优化和升级,欢迎朋友们前来体验,给短说提出宝贵的意......
  • macOS Sequoia 15.0 (24A335) 正式版发布,ISO、IPSW、PKG 下载
    macOSSequoia15.0(24A335)正式版发布,ISO、IPSW、PKG下载iPhone镜像、Safari浏览器重大更新、备受瞩目的游戏和AppleIntelligence等众多全新功能令Mac使用体验再升级请访问原文链接:https://sysin.org/blog/macOS-Sequoia/,查看最新版。原创作品,转载请保留出处。作者......
  • 红抖AI助手v2.5.0热点文案一键创作Ai工具,小红书,抖音爆款仿写
    摘要本文介绍了一款适用于Android端的自媒体内容提取工具,该工具支持从多个流行平台提取内容,并具备批量创作功能,旨在提高自媒体创作效率。1.工具概述自媒体批量创作内容提取工具是一款专为自媒体创作者设计的辅助工具,支持从小红书、抖音、微博、哔哩哔哩等平台提取内容,......
  • 红抖AI助手v2.5.0热点文案一键创作Ai工具,小红书,抖音爆款仿写
    摘要本文介绍了一款适用于Android端的自媒体内容提取工具,该工具支持从多个流行平台提取内容,并具备批量创作功能,旨在提高自媒体创作效率。1.工具概述自媒体批量创作内容提取工具是一款专为自媒体创作者设计的辅助工具,支持从小红书、抖音、微博、哔哩哔哩等平台提取内容,......
  • 红抖AI助手v2.5.0热点文案一键创作Ai工具,小红书,抖音爆款仿写
    摘要本文介绍了一款适用于Android端的自媒体内容提取工具,该工具支持从多个流行平台提取内容,并具备批量创作功能,旨在提高自媒体创作效率。1.工具概述自媒体批量创作内容提取工具是一款专为自媒体创作者设计的辅助工具,支持从小红书、抖音、微博、哔哩哔哩等平台提取内容,......
  • 红抖AI助手v2.5.0热点文案一键创作Ai工具,小红书,抖音爆款仿写
    摘要本文介绍了一款适用于Android端的自媒体内容提取工具,该工具支持从多个流行平台提取内容,并具备批量创作功能,旨在提高自媒体创作效率。1.工具概述自媒体批量创作内容提取工具是一款专为自媒体创作者设计的辅助工具,支持从小红书、抖音、微博、哔哩哔哩等平台提取内容,......
  • 这才是我想要的PCIe 5.0 SSD!慧荣SM2508主控首测:读写满血 还不烫手
    市面上现有的PCIe5.0SSD几乎都采用了群联E26主控,不但读写速度达不到满血标准,最高也就12GB/s,功耗和发热还特别高,经常需要主动风扇散热。英韧IG5666性能好了不少,基本可以跑满,但是发热仍然太高,因为它俩都是台积电12nm。慧荣已经多次展示过他们的方案SM2580,一方面性能满血,一方面发......
  • Cisco Jabber 15.0 发布下载 - 面向企业的多合一通信工具
    CiscoJabber15.0(Andriod,iOS,macOS,Windows)-面向企业的多合一通信工具即时消息、语音和视频通话、语音邮件、桌面共享、会议和在线状态请访问原文链接:https://sysin.org/blog/cisco-jabber-15/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org思科Jabber......
  • Centos7怎么安装Redis5.0
    Centos7怎么安装Redis5.0转载:https://www.php.cn/faq/553616.htmlWBOY发布:2023-06-0119:08:49转载1737人浏览过 一、安装gcc依赖由于 redis 是用C语言开发,安装之前必先确认是否安装gcc环境(gcc-v),如果没有安装,执行以下命令进行安装 [root@localho......
  • Elasticsearch 集群 和 Kibana:最新版 8.15.0 手动安装教程
    1.前言Elasticsearch和Kibana是ElasticStack的核心组件,分别扮演着数据存储与检索、分析和数据可视化的角色。‌1.1Elasticsearch‌简介Elasticsearch‌是一个基于JSON的分布式搜索和分析引擎,它提供了一个分布式、多租户能力的全文搜索引擎,具有HTTP网络接口和无模式......