NTT线性卷积定义：\[(f*g)[i]=\sum_{j=0}^{i}f[j]\cdotg[i-j]\]卷积定理：\[\mathcal{F}(f*g)=\mathcal{F}(f)\cdot\mathcal{F}(g)\]于是，求线性卷积可以转化为，先变换，再直接相乘，最后逆变换。注意：序列长度须变成N+M-1，对齐2^k。循环卷积（圆周卷积）一般用于两个等长序

dzk在做蛋糕上的草莓是蛋糕的灵魂这道题的时候写的\(longlong\)爆了，补题的时候经lwq指点，学习了__int128的用法int最大值\(2^{32-1}-1\)longlong最大值\(2^{64-1}-1\)__int128最大值\(2^{64-1}-1\)关于__int128：只能进行四则运算，不能用cin和cout来输出，不能用位运算来

P9755[CSP-S2023]种树迟来的补题本题是让最小化所有树长到指定高度日期的最大值，于是想到二分答案。那么，对于一个给定的期限\(x\)，如何判断是否能在这个日期内完成任务呢？首先我们发现前\(n\)天每天都要种树，那么假设我们已经知道了每个地块最晚哪个日期种树，能保证在期限\(x\)

打的稀烂，但是还是上分了（A考虑对值域做一个后缀和。若某一个后缀和的值是奇数那么先手就可以获胜。否则就不可以获胜。（我才不会告诉你我这题吃了一次罚时的）#pragmaGCCoptimize(3)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intmysqrt(intx){

目录简介支持运算输入输出例题简介\(\_\_int128\)并不是标准c/c++中的数据类型，而是一些特定编译器如gcc/g++提供的扩展数据类型。支持运算\(\_\_int128\)的是有符号128位整数变量，最多表示39位整数。支持基本的加减乘除运算，以及按位与&、按位或|、按位异或^、左移<<、右移>

引言：__int128不能用\(cin\)\(cout\)或\(scanf\)\(printf\)。快读思想：把每一个字符读入，组成数字。intread(){ intx=0,y=1;//x代表那个数的绝对值，y代表符号 charch=getchar(); while(ch<'0'&&ch>'9'){//如果字符不是数字 if(ch=='-')y=-1;

前置知识中国剩余定理（CRT），逆元；EXCRT是什么我们知道对于\[\begin{equation} \begin{cases} x\equivc_1\(mod\m_1)\\ x\equivc_2\(mod\m_2)\\ .\\ .\\ .\\ x\equivc_i\(mod\\m_i)\\ \end{cases}\end{equation}\]一个一元线性同余方

前置知识中国剩余定理（CRT），逆元；EXCRT是什么我们知道，对于对于\[\begin{equation} \begin{cases} x\equivc_1\(mod\m_1)\\ x\equivc_2\(mod\m_2)\\ .\\ .\\ .\\ x\equivc_i\(mod\\m_i)\\ \end{cases}\end{equation}\]一个一元线性

\(\large\textbf{Statement.}\)求出最小的非负整数\(m\)，使得：\[\left|x-\sum_{i=0}^{m-1}x_{i\bmodn}\right|+\left|y-\sum_{i=0}^{m-1}y_{i\bmodn}\right|\lemk\]\(\large\textbf{Solution.}\)考虑枚举\(m\bmodn\)，然后求和就转化成了一段前缀和加上整个序列和的若

普通的CRT只能处理模数两两互质的情况，而EXCRT可以求得任意情况下同余方程组的通解。思想：把两个同余方程合并成一个，直到剩下一个。考虑两个同余方程\(x\equivp_1\pmod{m_1},x\equivp_2\pmod{m_2}\)。则\(x=p_1+m_1A=p_2+m_2B\)。移项得\(m_1A-m_2B=p_2-p_1\)。这是

inlinevoidread(__int128&x){x=0;intf=1;//判断正负charch=getchar();//读入字符while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&

C.SashaandtheCasino当\(k<x\)时,显然我们只需要每次下注一个硬币就好了.当\(k>x\)时.考虑先一个一个的下硬币,那么为了保证不亏本,最多输\(k-2\)局,然后在第\(k-1\)局赢,这样才能盈利\(1\)个硬币.那么在第\(k\)局之后呢?此时我们最少也需要下注两个硬币,这

定义坐标型动态规划一般是给定网格、序列，求满足条件的MAX或MIN。开数组时，dp[i]一般代表以ai结尾的满足条件的子序列，dp[i][j]代表以i、j结尾的满足条件的最优解例题数塔典中典变形晴天小猪历险记之Hill抓苹果免费馅饼矩阵取数描述传送门思路首先看出，每行的问题是独立

\(\mathbf{Part\0}\)目录\(/\\mathbf{Contents}\)\(\mathbf{Part\1}\)题目大意\(/\\mathbf{Item\content}\)\(\mathbf{Part\2}\)题解\(/\\mathbf{Solution}\)\(\mathbf{Part\2.1}\text{C}\)++神奇整数类型之\(\text{__int128}/

 //读入inline__int128read(){__int128x=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0&#

解题思路激光塔一定在最后。\(f_{i,j}\)表示前\(i\)个位置放\(j\)（\(j\lei\)）个放射塔，那么\(i-j\)个干扰塔的伤害。若第\(i\)个位置放放射塔：\(f_{i,j}=f_{i-1,j-1}+(j-1)\timesg\times[t+b\times(i-j)]\)若第\(i\)个位置放干扰塔，也就是\(j<i\)：\(f_{i,j}=\max\{f_{i-

前言一个月前的一场悲剧qwq传送门没事干写的qwq热乎着的一道题，昨晚上刚考完，然而这是一场悲剧。。。。题解题目大意给定\(a_1~a_n\)和\(c\)，求\((a_1+2\timesw)^2+(a_2+2\timesw)^2+...+(a_n+2\timesw)^2=c\)时\(w\)的最小值解析我们来化简一下这个式子：\((a_

题意：给定\(n,a,b,c,x\)，求满足\(1\lei,j,k\len\)且\(ai+bj+ck=x\)的三元组\((i,j,k)\)的个数。\(1\len\le10^6\)，\(1\lea,b,c\le10^9\)，\(1\lex\le3\times10^{15}\)。考虑到\(n\)只有\(10^6\)级别，我们可以枚举\(i\)来消掉\(ai\)，这样就变成了求\(

The2022ICPCAsiaRegionalsOnlineContest(II)EAnInterestingSequence232323232323323232323232#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;voidsolve(){ lln,k; cin>>n>>k; llres=k; llt=0; for(

1.进制转换1.1（10转其他进制）stringintToA(intn,intradix)//n是待转数字，radix是指定的进制{ stringans=""; do{ intt=n%radix; if(t>=0&&t<=9) ans+=t+'0'; elseans+=t-10+'a'; n/=radix; }while(n!=0); //使用do{}while（）以防止

solved:3rank:C.Congruences题意:对于每组数据给定M个pi和qi,pi为两两不同的质数,N为所有pi的积,问是否存在最小的正整数x使得xpi在模N的意义下与qi同余可以推出xpi在模pi的意义下与qi同余在模N的意义下与qi同余,如果存在输出x,否则输出-1;显然xpi在模N的意义下与qi同余可以

inline__int128read(){__int128x=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0�

P6205[USACO06JAN]DollarDayzS-洛谷|计算机科学教育新生态(luogu.com.cn)题解：完全背包,__int128，傻逼题#include<bits/stdc++.h>usingnamespacestd;__int128f[10001];voidwrite(__int128x){if(x>9)write(x/10);putchar(x%10+'0');}intmain(

exgcd点击查看代码__int128exgcd(__int128as,__int128bs,__int128&x,__int128&y){if(bs==0){x=1;y=0;returnas;}__int128ans=exgcd(bs,as%bs,y,x);y-=(as/bs)*x;returnans;}a&c&lucas点击查看代码

P4942小凯的数字题目和数据范围提示有\(O(1)\)作法。直接拆数字，会TLE$res\mod9=l(l+1)(l+2)...(r-1)r\mod9$找规律不难发现\(\texttt{所有数位的数字之和}\mod9\)即为答案。但直接求所有数位之和明显不行，（数位dp好像可以，也许吧没试过）观察到不需要求出所有