首页 > 其他分享 >新赛道-2024.8 CSP-J组月赛-T1总结

新赛道-2024.8 CSP-J组月赛-T1总结

时间:2024-09-01 10:47:25浏览次数:13  
标签:赛道 cout 2024.8 王老师 unsigned long T1 op mod

题面:

王老师 最近做了一道经典问题《翻纸牌》

现在 王老师 有 n 张牌,编号分别为 1,2,3…n,每张牌一开始都是背面朝上的

现在他要进行 n 轮操作,第 i 轮操作时候,他会将所有编号是 i 的倍数的牌正反翻面

现在 王老师 想知道,当他进行完 n 轮操作以后,所有正面朝上的牌的编号总和是多少

因为数字可能很大,所以请你将答案对 109+7 取模

对于 30% 的数据:1≤n≤106

对于 60% 的数据:1≤n≤1014

对于 100% 的数据:1≤n≤1018

从题中可知将n翻面的只有n的因子,而翻到正面的数字的因子个数一定是奇数,也就是完全平方数,再套入公式:n*(n+1)*(2*n+1)/6即可,但数据量为1e18,这么算会爆long long (我就是这么写挂的。。),所以需要用到特殊处理,首先,我们知道n*(n+1)%2==0,所以可以先算n*(n+1)/2,剩下的/3分两种情况讨论

设v=sqrt(n),x=v*(v+1)/2

1.若x%3==0,那么直接先将x/3%mod*(2*v+1)%mod;

2.否则把/3丢给(2*v+1):x%mod*((2*v+1)/3)%mod

代码:

#include <bits/stdc++.h>
using namespace std;
const unsigned long long mod=1e9+7;
unsigned long long n;
int main(){
  //freopen("card.in","r",stdin);
  //freopen("card.out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  cin>>n;
  unsigned long long op=sqrt(n);
  unsigned long long ans=op*(op+1)/2;
  if(ans%3==0)cout<<ans/3%mod*(2*op+1)%mod;
  else cout<<ans%mod*((2*op+1)/3)%mod;
  return 0;
}

标签:赛道,cout,2024.8,王老师,unsigned,long,T1,op,mod
From: https://www.cnblogs.com/qianqian2022/p/18391092

相关文章

  • Burp Suite Professional 2024.8 发布下载,新增功能概览
    BurpSuiteProfessional2024.8(macOS,Linux,Windows)-Web应用安全、测试和扫描BurpSuiteProfessional,Test,find,andexploitvulnerabilities.请访问原文链接:https://sysin.org/blog/burp-suite-pro/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgBur......
  • 2024.8.31 总结(集训 考 DP)
    今天依然是上午考DP,三个小时四道题。我觉得今天的题目较昨天更简单。考场上就想出了四个题,但是我以为T1\(O(n^3)\)的做法是暴力,想了好久T1也没想出更好的做法,于是开写,然后造数据测了测,发现跑得比较快(极限数据应该也是能在我的位置上那台电脑里1s内过的)。结果出分是330,......
  • 2024.8.31随笔
    前言开学了,不能每天写东西发博客了,但是我还是准备拿笔记录一下每一天的东西,总之最近还不会停课,可以放松一段时间。但是文化课也不能落下啊喵!自习这段时间除了最开始写了一篇字符串的博客,其他时间都在写dp题。然后坚持写做题的感想和题解,虽然今天没有遇到好题,或者说看到题但没......
  • 2024.8.31杂记
    P1249最大乘积题目描述一个正整数一般可以分为几个互不相同的自然数的和,如\(3=1+2\),\(4=1+3\),\(5=1+4=2+3\),\(6=1+5=2+4\)。现在你的任务是将指定的正整数\(n\)分解成若干个互不相同的自然数(也可以不分解,就是这个数字本身)的和,且使这些自然数的乘积最大。输入格式只一个正整......
  • 手把手在STM32F103C8T6上构建可扩展可移植的DHT11驱动
    前言如何驱动一个你陌生的传感器呢?别看我,也别在网上死马当活马医!你需要做的,首先是明确你的传感器的名称,在这里,我们想要使用的是DHT11温湿度传感器可能需要的前置知识简单的OLED驱动原理简单的IIC通信知识基础的查手册能力相对稳固的C语言基础不会没关系,我会详细......
  • FIT1047 Introduction to computer systems, networks and security
    FACULTYOFINFORMATIONTECHNOLOGYFIT1047Introductiontocomputersystems,networksandsecurity–S22024Assignment2–ProcessesandMARIEProgrammingPurposeProcessesandprogramsarewhatmakecomputersdowhatwewantthemtodo.Inthefirstp......
  • 2024.8.30 总结(集训 考 DP)
    上午三个多小时考四道题的DP。赛时会的分:[100](?)+100+[30](?)+100。估分:100+100+0+100。实际分:10+100+0+100。挂巨量的分,挂了120分。下面是一些值得注意的点:T1就是分组背包。DP数组下标要考虑负数可以直接全体加一个值变成非负的,[或者用map之类的](?)(&不......
  • Study Plan For Algorithms - Part16
    1.下一个排列题目链接:https://leetcode.cn/problems/next-permutation/整数数组的一个排列就是将其所有成员以序列或线性顺序排列。整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组......
  • 小尺寸BLE 5.2低功耗串口透传蓝牙模块 - ANS-BT103M
    ANS-BT103M是安朔科技自主开发的一款小尺寸BLE蓝牙5.2模块,它支持HID、GATT、ATT和其他配置文件,使用UART作为编程接口,用户可以使用AT命令通过UART读取或写入模块的配置,支持空中升级。支持蓝牙主从一体,一对多连接,透传速率可达60KB/s,支持定制开发。产品参数:模块型号      ......
  • 第九章 动态规划Part12
    目录任务115.不同的子序列思路583.两个字符串的删除操作思路72.编辑距离思路任务115.不同的子序列给你两个字符串s和t,统计并返回在s的子序列中t出现的个数,结果需要对10^9+7取模。思路dp[i][j]表示s[0:i)中出现以t[0,j)的次数每次拓展一个字符,求次数,直到拓......