关闭
当前搜索:

[杜教筛][莫比乌斯反演] LOJ #6229. 这是一道简单的数学题

SolutionSolution 求∑i=1n∑j=1iij(i,j)2\sum_{i=1}^n\sum_{j=1}^i{ij\over(i,j)^2}可能算是裸题? 相当于求12∑d=1n(d[d=1]+d2φ(d))⌊nd⌋{1\over2}\sum_{d=1}^n\big(d[d=1]+d^2\varphi(d)\big)\lfloor{n\over d}\rfloor 关于idn⋅φ...
阅读(19) 评论(0)

[FFT][离散对数][原根] LOJ #6156. A * B Problem

SolutionSolution 刚开始看错题了。。。其实就是一个FFT裸题 如果p∤a,p∤bp\nmid a,p\nmid bab≡k(modp)ab\equiv k\pmod p是与logGa+logGb≡logGk(modφ(p))log_Ga+log_Gb\equiv log_Gk\pmod{\varphi(p)}等价的吧。。 那找个原根就好啦。。模pp等于00的特判一下 爆in...
阅读(31) 评论(0)

[最大团][二分图] LOJ #526. 「LibreOJ β Round #4」子集

SolutionSolution 边(i,j)(i,j)存在当且仅当[(ai,aj)≠1∨(ai+1,aj+1)≠1][(a_i,a_j)\neq1\vee(a_i+1,a_j+1)\neq1]。 就等价于求最大团。 随机乱搞好像这种题都过不了qwq 发现一个性质,aia_i与aja_j奇偶性相同时是必定有边的。考虑补图的最大独立集,显然这是一个二分图,跑最大匹配就好啦。 #incl...
阅读(20) 评论(0)

[FWT][DP] UOJ #310. 【UNR #2】黎明前的巧克力

SolutionSolution DP很好想。 设ii个巧克力的集合幂级数fif_i,其中fi,0=1,fi,ai=2f_{i,0}=1,f_{i,a_i}=2。 答案就是这一堆东西对称差卷积起来。 暴力的做法就是把每个都FWT一下再乘起来。 集合幂级数ff的沃尔什变换fS^=∑T⊆U(−1)|S∩T|fT\hat{f_S}=\sum_{T\subseteq U}(-1)^{|S\cap...
阅读(32) 评论(0)

[Contest]CodeChef January Challenge 2018

RECTANGL:学习了ifif语句的用法。 MAXSC:贪心。 KCON:贪心。 PRTITION:乱搞题。 STRMRG:O(n2)O(n^2)DP。 MONSTER:整体二分+暴力。。 XYHUMOQ:奇妙的搜索。。设f0,f1,g0,g1f_0,f_1,g_0,g_1分别表示前(后)一半以0/10/1结尾(开头)方案数相应的操作的最小值。就有g0=x−(f0+1)(g1+1)+...
阅读(31) 评论(0)

[子集DP][Lucas定理] BZOJ 4903: [Ctsc2017]吉夫特

SolutionSolution 原来可以把简单的题面写的那么长~ 根据Lucas定理,(nm)≡(⌊n2⌋⌊m2⌋)(nmod2mmod2)(mod2){n\choose m}\equiv {{\lfloor{n\over2}\rfloor}\choose{\lfloor{m\over2}\rfloor}}{n\bmod2\choose m\bmod 2}\pmod2有(00)=1,(01)...
阅读(35) 评论(0)

[最小割] ARC 074 F - Lotus Leaves

SolutionSolution 这样建图:对每一行每一列都建一个点,连向行内的荷叶。 那这道题就相当于删去最少的点使得源汇点不连通。 按这里一样建图就好了。 又忘记写当前弧优化了 #include using namespace std; const int N = 233; const int INF = 1 28; struct edge { int to, ca...
阅读(40) 评论(0)

[DP] ARC074 E - RGB Sequence

SolutionSolution dpr,g,bdp_{r,g,b}表示考虑前max{r,g,b}max\{r,g,b\}个格子,三种颜色最后一次放在r,g,br,g,b位置的方案数。 把不合法的(r,g,b)(r,g,b)三元组ban掉就好了。 #include using namespace std; const int MOD = 1000000007; const int N...
阅读(32) 评论(0)

[数论][构造][离散对数] Codeforces 913 G. Power Substring

SolutionSolution 设aa长度为nn。 可以尝试构造一个数bb,使得a⋅10m+ba\cdot10^m+b成为其后缀。 就等价于x=a⋅10m+b≡2k(mod10n+m)x=a\cdot10^m+b\equiv2^k\pmod {10^{n+m}} 构造k≥n+mk\ge n+m,那要满足这样的kk就等价于2n+m∣x∧5∤x2^{n+m}\mid x\wedge5\nmi...
阅读(73) 评论(0)

[回文自动机][树形DP] CodeChef PALPROB

SolutionSolution 建出回文自动机,每个节点再维护一个halfuhalf_u指针,指向长度不超过⌊lenu2⌋\lfloor{len_u\over2}\rfloor的最长回文后缀。 树形DP出每个点的nessness表示回文指数,答案就是∑nessu∗|rightu|\sum ness_u*|right_u|。 failfail链上的节点的lenvlen_v一定是递减的。可以倍...
阅读(51) 评论(0)

[回文自动机][阈值] BZOJ 4932: 基因

SolutionSolution 关于回文自动机的前端插入:一个回文串的回文前缀显然是其回文后缀。实现两端插入需要记录两个指针lastback,lastfrontlast_{back},last_{front},注意当最长回文前(后)缀为原串时,两个指针就相同了。 一个串的子串的回文自动机是这个串的回文自动机的子图。因为增量法构造回文自动机时是不会改变原有的自动机的。 这道题的话阈值B=n...
阅读(68) 评论(0)

[回文自动机] BZOJ 3676: [Apio2014]回文串

SolutionSolution 回文自动机有很多性质是和后缀自动机很相似的。 这个题可以类似于SAM,在每个节点uu维护一个righturight_u。答案就是max{|rightu|∗lenu}max\{|right_u|*len_u\} 关于回文自动机的复杂度,可以势能分析。 #include using namespace std; const int N = 303030;...
阅读(41) 评论(0)

[博弈论][凸包][复杂度分析] SRM 597 Div1 Medium ConvexPolygonGame

SolutionSolution 设WiW_i为第ii次操作后可以得到的凸多边形的集合。 显然有Wi⊆Wj,i>jW_i\subseteq W_j,i\gt j。 所以如果最开始不能操作则先手必败,否则先手必胜。 问题就在于判断凸多边形中是否存在三点不共线。 暴力判断是O(X2)O(X^2)的。 转化成任意三点共线,这样的点数不超过max(maxX−minX,maxY−minY)max...
阅读(43) 评论(0)

[树形DP] SRM 598 Div1 Hard TPS

SolutionSolution 可以枚举根,在根放一个信标,就可以区分出深度不同的点。 若在节点uu放信标,则可以区分出点vv是否在uu内。可以考虑从disu,v=depu+depv−2deplca(u,v)dis_{u,v}=dep_u+dep_v-2dep_{lca(u,v)}求出deplca(u,v)dep_{lca(u,v)},再与depudep_u比较即可。 若节点uu的两个子树...
阅读(42) 评论(0)

[组合数] SRM 555 Div1 Medium XorBoard

SolutionSolution 枚举行列进行奇数次操作的个数,组合数算一下就好了。 // BEGIN CUT HERE // END CUT HERE #line 5 "XorBoard.cpp" #include using namespace std; const int N = 3333; const int MOD = 555555555; typedef long lon...
阅读(39) 评论(0)
185条 共13页1 2 3 4 5 ... 下一页 尾页
    个人资料
    • 访问:30400次
    • 积分:2297
    • 等级:
    • 排名:第18827名
    • 原创:185篇
    • 转载:0篇
    • 译文:0篇
    • 评论:0条
    友情链接