- 2024-08-18CF1946E Girl Permutation
中文题面:https://www.luogu.com.cn/problem/CF1946E先考虑只要求前缀最大值怎么做。从前往后很容易想到\(O(n^3)\)的dp,用前缀和优化可以到\(O(n^2)\).注意相对顺序,\([p_i,p_{i+1}-1]\)选择的数,必须让最大的放在最前面才合法。比如选1,3,9,在[5,8]这个区间,只有9,1,3和9,3,1是合法
- 2024-08-15AT_agc025_b RGB Coloring 题解
ProblemSolution由于涂绿色的得分为\(A+B\),所以可以将红色与蓝色独立考虑。依次枚举红色的个数,假定为\(i\),所以剩余需要的得分为\(K-i\timesA\),判断是否能被\(B\)整除,若能,则蓝色个数为\(\frac{K-i\timesA}{B}\),设为\(j\),则总方案累加\(C^{i}_{n}\timesC^{j}_{n}\),除
- 2024-08-13Codeforces Round 964 (Div. 4)
###A.```c++#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+7;voidsolve(){ intx; cin>>x; cout<<x/10+x%10<<endl;}intmain(){ intT; cin>>T; while(T--)solve();
- 2024-08-10逆元
逆元用于求$\frac{a}{b}(mod\p)$的结果第一种方法:拓展欧几里得利用拓欧求解同余方程:\(a*x≡c\(mod\b)\)的\(c=1\)的情况就可以转化成求解\(a*x+b*y=1\)这个方程voidexgcd(lla,llb,ll&x,ll&y)//解ax+by=gcd(a,b)的一组整数解{ if(b==0) {
- 2024-08-06八月总结复习
20240806kmpmanacherac自动机20240806线性求逆元假设我们求取\(n\)关于质数\(p\)的逆元,即求取\(n^{-1}\)我们设\(a=\lfloorp/n\rfloor,b=p\modn\)。则有$a*n+b\equiv0(mod\p)$移项可得:\[a*b\equiv-b(mod\p)\]\[-a/b\equivn^{-1}(mod\p)\]即:\[n^{-1}\e
- 2024-07-31游戏
要统计差值为k的数对(i,j)的数量,这种感觉类似于卷积,我们把和差放到幂次中体现,就可以用NTT做到O(ailogai)其中,对于差值为0的特殊情况,不仅需要减去数自匹配的n种情况,还要除以2NTT要预处理step+倍增法优化,否则会TLE将游戏每轮的操作抽象为数学函数点击查看代码#include<bits
- 2024-07-30P3811 【模板】模意义下的乘法逆元 题解
【模板】模意义下的乘法逆元题目背景这是一道模板题题目描述给定n,pn,pn,p求
- 2024-07-22P6475 [NOI Online #2 入门组] 建设城市
P6475[NOIOnline#2入门组]建设城市传送门分类讨论:设\(f(x,y)\)为\(C^{j-1}_{i+j-1}\)\(x,y\)在同一旁把\(x,y\)之间的看成一个高楼公式\(f(n,m)\timesf(n+x-y,m)\)\(x,y\)在异侧枚举\(x,y\)高楼的高度\(h\)\(\displaystyle\sum^{n}_{i=1}f(x-1,i)*f(n-x,m-i
- 2024-07-18优化原理 (1)高斯牛顿 线性
/**Gauss-Newtoniterationmethod*author:Davidwang*date:2020.08.24*/#include<iostream>#include<chrono>#include<opencv2/opencv.hpp>#include<Eigen/Core>#include<Eigen/Dense>usingnamespacestd;u
- 2024-07-09思考 Count The Repetitions,谈谈对 T2乒乒球的认识
思考什么什么不写题意共记录了\(n\)颗球胜负关系,给出\(n\)和其长度为\(k\)的循环节,求最终比分。思路首先特判答案为\(0:0\)的情况:循环节与AB或ABBA同构。然后暴力找比分的周期,因为令任意位置作为一局起点时该局终点唯一,反之亦然,所以复杂度\(O(\left|state\ri
- 2024-07-09【信息融合与状态估计】时滞系统的协方差交叉融合估计研究(Matlab代码实现)
- 2024-07-03AT_dp_y Grid 2 题解
题目传送门前置知识计数DP|排列组合解法正难则反,考虑求出总方案数和至少经过一个黑色格子的方案数,二者作差即为所求。强制增加一个黑色格子\((h,w)\),使得存在一条至少经过一个黑色格子的路径。如果没有“不能移动到黑色格子中”的限制,那么就是一个简单的格路计数问题,方
- 2024-07-01基于自适应波束成形算法的matlab性能仿真,对比SG和RLS两种方法
1.程序功能描述基于自适应波束成形算法的matlab性能仿真,对比SG和RLS两种方法. 2.测试软件版本以及运行结果展示MATLAB2022a版本运行 3.核心程序forii=1:MTKLifSEL==1fori=1:length(r)
- 2024-06-23ecoAddRepeater -loc与-offLoadAtLoc的区别
我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧?拾陆楼知识星球入口 ecoAddRepeater-loc{xy}-cellBUF-netNET ecoAddRepeater-offLoadAtLoc{xy}-cellBUF-netNET 都是指定插buf/inv物理位置,区别在于前者用于插buf/inv驱动原始net所有的inputterm,后
- 2024-06-20基于cadence最基础的inv和and保姆级教学
- 2024-06-14ncverilog与finesim联合进行混合仿真的详细过程(以spice为顶层)
第一步:Makefile仿真命令one:ncverilog+access+rwc+nc64bit+loadvpi=finesim.so:finesim_startup-frun.f第二步:环境结构(1)以模拟为顶层,顾名思义是把CDL网表中某一个模块替换为数字的function,其余全是CDL,以上图为例,把其中inv替换为数字的function。(2)需要文件:testben
- 2024-06-12CF1204E = 998244853.
CF1204E=998244853.Natasha,SashaandthePrefixSumsNaCly_Fish最喜欢的数字是\(n\)和\(1\);\(\mathsfE\color{red}\mathsf{ntropyIncreaser}\)最喜欢\(m\)和\(-1\)。有一天,她们在一起写出了一个长度为\(n+m\),有\(n\)个\(1\)和\(m\)个\(-1\)的序列\(
- 2024-06-11计树 Normal --
无聊的水题。无聊的水题IDLS喜欢上树。但是他并不想把一道数据结构题出到树上,他喜欢计Tree。这一天,他想自己造一棵树,他手头有\(N\)个树的节点,标号为\(1\simN\),他会在它们之间连边,我们定义两颗树不同,当且仅当一对节点在一棵树中有连边,另一棵树中没有连边。但他不喜欢
- 2024-06-11由AtCoder_ABC357D引发的除法同余学习
鉴于最近的Atcoder周赛又出现除法求余,下定决心学习逆元相关内容同余概述定义同余定义:若a和b是整数,且m|(a-b),则称a和b模m同余。即两者除以m得到的余数相同。剩余系:一个模m完全剩余系是一个整数集合,任何一个整数恰好与该集合中的一个元素模m同余。例如0,1,...,m-1的集
- 2024-05-22P4859 已经没有什么好害怕的了
P4859已经没有什么好害怕的了二项式反演看到恰好,求方案数,可以想到二项式反演。套路钦定\(k\)组糖果比药片能量大,其他任意组合,这样的方案数记为\(g_k\)。再设\(f_k\)表示恰好\(k\)组的糖果比药片能量大的方案数,现在要找到\(g\)和\(f\)之间的关系。容易推出\(g_k=\s
- 2024-05-05CF1967C. Fenwick Tree-算子展开,树状数组的结构
link:https://codeforces.com/problemset/problem/1967/C题意:定义\(f(a)=s\)中的\(f\)表示把序列\(a\)映射为其树状数组的操作(\(s\)就是对应的树状数组),并且操作是在取模下作的,已知\(f^k(a)=b\),已知序列\(b\)和自然数\(k\),求\(a\).\(1\leqn\leq2\times10^5,1\leq
- 2024-04-28低开销求补码电路
电路里经常用补码来表示有符号整数,求一个负数的补码表示最直接的方法是将对应的正数取反再加1。如果要写一个参数化的求补码的模块,则代码如下:modulecal_complement#(parameterWIDTH=8)(input[WIDTH-1:0]din, output[WIDTH-1:0]dout); assigndout=~(di
- 2024-04-22CF1957E 做题小计 : 威尔逊定理
被数论虐爆了(悲)威尔逊定理\(\forallp\inprime,(p-1)!\equiv-1(\bmodp)\)为什么啊?对于\(2\)很显然。对于\(p\),我们知道\(inv(p-1)=p-1=-1\),然后\(inv(1)=1\)然后因为\(p\inprime\),所以对于任意\(a\in[2,p-2]\),都有\(inv(a)\)与它唯一对应。因为\(
- 2024-04-14牡牛和牝牛
原题来自:USACO2009Feb.Silver牡mǔ,畜父也。牝pìn,畜母也。——《说文解字》约翰要带n只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有k只牝牛。请计算一共有多少种排
- 2024-04-14记录一下
在预处理逆元的时候,需要给inv[0]赋值为1,虽然0的逆元为0(或是无意义)但计算inv[m]*inv[n-m]%p时为避免(m==n)导致误差所以要去给inv[0]赋值1但单点求就不用,因为fact[0]=1已经避免这种情况即qpow(fact[m]*fact[n-m],p-2,p)中fact[m]*fact[n-m]不会因为n==m而造成误差变成0还有就