RedGrey的博客

循环最长公共子序列 参考：https://arxiv.org/pdf/1208.0396.pdf 问题描述 我们需要求两个循环序列的最长公共子序列，对于循环序列来说，把任意一个元素作为起始元素都认为是同一个序列，例如，循环序列’algorithm’同时也可以写作’rithmalgo’或者’thmalgori’，对于正常的序列’algorithm’和’grammar’来说，最长公共子序列为’grm’，但是对于循环序列来说，它们的最长公共子序列是’grma’ 预备知识 对于普通的非循环序列的最长公共子序列来说，记两个序列分别为A,BA,BA,B，AAA的元素个数为mmm，BBB的元素个数为nnn，例如AAA为BBAABBAABBAA，BBB为ABABBABABBABABB，可以将其转化为有向图，每个单元格可以看作图中的一个节点，向右或者向下可以连一条边，对于单元格(i,j)(i,j)(i,j)来说，如果A[i]A[i]A[i]和B[j]B[j]B[j]的元素相同，则从(i−1,j−1)(i-1,j-1)(i−1,j−1)向(i,j)(i,j)(i,j)斜着连一条边，如下图所示，记该有向图 ...

凸包技巧 参考：https://codeforces.com/blog/entry/63823 问题描述 我们想要快速地计算对于某个固定的xxx，下述算式集合中的最大值： maxj∈S(kj∗x+bj)max_{j \in S}(k_j*x+b_j) maxj∈S​(kj​∗x+bj​) 此外，插入一个新的jjj对应的算式到集合中也应该需要高效地完成。 思路 注意算式kj∗x+bjk_j*x+b_jkj​∗x+bj​的形式，它相当于斜率为kjk_jkj​，与yyy轴交点为kjk_jkj​的直线，所以这个问题就相当于是给定一系列直线与一个特定的xxx值，求在横坐标为xxx时，这一系列直线中最大的yyy值；如果将所有的直线画出来，你会发现最大值将是一个凸包的边缘，如下图所示： 一些观察到的结论 在凸包上的每一条线都在一段连续的xxx值区间内是最大值，相反，不在凸包上的线是无用的，这些线永远不会是最大值 在凸包上所有线的斜率都不一样，斜率的顺序同时决定了他们在凸包上的位置。斜率值较小的线在凸包上位于斜率比它大的线的左侧 因此，一个可行的策略是只维护凸包上的线，而不保存那些无用的线 一 ...

集合的二进制表示法 概述 有一个包含nnn个不同元素的集合，假设为：{1,2,3,..,n}\{1,2,3,..,n\}{1,2,3,..,n}，他的子集个数有2n2^n2n个，当nnn的大小不是特别大的时候，例如n≤30n\le 30n≤30时（约等于107374182410737418241073741824），我们则可以在合理的时间内枚举出它的所有子集。 子集的表示方法 数组表示法 直接用数组表示集合，这种表示方式比较直接，c++中的任何容器类型都可以用来存储集合 01 bit串表示法（二进制表示法） 使用一个整数的二进制形式来表示集合，二进制数第i个bit位为0，则表示全集中的第i个元素不在子集中，二进制数第i个bit位为1，则表示在子集中；例如一个包含3个元素的集合{1,2,3}的所有子集，可以用<8的整数来表示： 0 -> 000 -> {} 1 -> 001 -> {1} 2 -> 010 -> {2} 3 -> 011 -> {1,2} 4 -> 100 -> {3} 5 -&g ...

原题链接：https://atcoder.jp/contests/dp/tasks/dp_j J - Sushi Time Limit: 2 sec / Memory Limit: 1024 MB Problem Statement There are N dishes, numbered 1,2,…,N1,2,…,N1,2,…,N. Initially, for each i(1≤i≤N)i(1≤i≤N)i(1≤i≤N), Dish iii has ai(1≤ai≤3)a_i(1≤a_i≤3)ai​(1≤ai​≤3) pieces of sushi on it. Taro will perform the following operation repeatedly until all the pieces of sushi are eaten: Roll a die that shows the numbers 1,2,…,N1,2,…,N1,2,…,N with equal probabilities, and let iii be the outcome. If there ...

原题链接：https://cses.fi/problemset/task/2181 Counting Tilings Your task is to count the number of ways you can fill an n×mn×mn×m grid using 1×21×21×2 and 2×12×12×1 tiles. Input The only input line has two integers nnn and mmm. Output Print one integer: the number of ways modulo 109+710^9 +7109+7. Constraints 1≤n≤101\le n\le101≤n≤10 1≤m≤10001\le m\le10001≤m≤1000 Example Input: 14 7 Output: 1781 题目描述 有1∗21*21∗2大小的砖，可以横着铺也可以竖着铺，问有多少种不同方法，可以铺满n∗mn*mn∗m大小的网格（不考虑对称、翻转等情况） 解决方案 我们把短的边设为水平方向，长的边设为竖直方向，我们从 ...

原题链接：https://judge.yosupo.jp/problem/montmort_number_mod Montmort Number Let aka_kak​ be the number of size kkk permutations ppp s.t. pi≠ip_i \ne ipi​=i for each iii. Given N,MN,MN,M. For each i=1,⋯,Ni=1,⋯,Ni=1,⋯,N, print bk=akmod  Mb_k=a_k\mod Mbk​=ak​modM. Constraints 1≤N≤1061\le N \le 10^61≤N≤106 1≤M≤1091\le M \le 10^91≤M≤109 Input N M Output b1 b2 ... bnb_1 \ b_2\ ...\ b_nb1​ b2​ ... bn​ Sample #1 1210 1000 1 2 9 44 65 54 33 96 61 #2 1220 9982443530 1 2 9 44 265 1854 14833 133496 1334961 1 ...

原题链接：https://cses.fi/problemset/task/1079 Binomial Coefficients Your task is to calculate nnn binomial coefficients modulo 109+710^9+7109+7. A binomial coefficient (ab)\binom{a}{b}(ba​) can be calculated using the formula a!b!(a−b)!\frac{a!}{b!(a-b)!}b!(a−b)!a!​. We assume that aaa and bbb are integers and 0≤b≤a0≤b≤a0≤b≤a. Input The first input line contains an integer nnn: the number of calculations. After this, there are nnn lines, each of which contains two integers aaa and bbb. Output Print ...

来源：https://usaco.guide/CPH.pdf#page=217 概述 组合数学研究的是：如何对对象的组合进行计数，通常的目标是为了高效地计算出组合的个数，而不用单独生成每一个组合。 例如，考虑将一个正整数nnn拆分成≤n\le n≤n的正整数的和的方法个数（不同顺序视作不同方法），例如，对于4来说，有8种方法： 1+1+1+1 1+1+2 1+2+1 2+1+1 1+3 2+2 3+1 4 组合问题往往能够使用递归函数解决，例如上述问题，我们可以使用f(n)f(n)f(n)来代表拆分方法的个数，例如f(4)=8f(4)=8f(4)=8，f(n)f(n)f(n)可以使用如下公式递归计算得到 f(n)={1,n=11+f(1)+...+f(n−1),n>1f(n)= \left\{ \begin{array}{lr} 1 , & n=1 \\ 1+f(1)+...+f(n-1) , & n\gt 1 \end{array} \right. f(n)={1,1+f(1)+...+f(n−1),​n=1n>1​ 上述公式的含义是，如果选kkk作 ...

hexo基础环境搭建 https://zhuanlan.zhihu.com/p/102592286 1. 创建一个新的md文件 1$ hexo new "title" 该命令默认会在source/_posts下创建一个title.md文件 2. 本地测试 1$ hexo server 3. 生成静态html文件 1$ hexo generate or 1$ hexo g 4. 发布并上传到github 1$ hexo deploy or 1$ hexo d 如果hexo d执行失败，如果开了vpn或者代理，可能需要打开一个新的bash界面再次尝试执行该命令，因为老的bash可能使用了老的代理设置，需要打开一个新的bash刷新一下 1234567开启代理软件后设置代理git config --global http.proxy 127.0.0.1:7890git config --global https.proxy 127.0.0.1:7890取消代理git config --global --unset http.proxygit config --glob ...