11D_Beyonder's Blog

题目大意 给出多重数集 S=x1,x2,⋯ ,xnS={x_1,x_2,\cdots,x_n}S=x1​,x2​,⋯,xn​，求其所有大小为 kkk 的子集的 gcd⁡\gcdgcd 之积。共 TTT 组数据，要求答案  mod P\bmod PmodP 输出。 不保证 SSS 中所有数各不相同，不保证 PPP 为质数。T≤60,106≤P≤1014,1≤xi≤8×104,1≤∣S∣≤40000,1≤k≤min⁡(∣S∣,30)T≤60,10^6≤P≤10^{14},1≤x_i≤8\times 10^4,1≤|S|≤40000,1≤k≤\min(|S|,30)T≤60,106≤P≤1014,1≤xi​≤8×104,1≤∣S∣≤40000,1≤k≤min(∣S∣,30)。 思路 枚举所有可能出现的 gcd⁡\gcdgcd，设 gcd⁡=g\gcd=ggcd=g 的长度为 kkk 的子集个数为 cgc_gcg​，那么最终答案 $ans=\prod\limits_{g=1}^{\max\limits_{1\le i\le n}\{x_i\}}g^{c_g}$。我们的任务是求出每一个 cgc ...

G. Game of Swapping Numbers 题目描述 Given two arrays AAA, BBB with length NNN, you should perform exactly KKK operations in array AAA. For each operation, choose 222 elements AiA_iAi​, AjA_jAj​ (1≤i<j≤N1≤i<j≤N1≤i<j≤N​) and swap the positions of AiA_iAi​ and AjA_jAj​. Please maximize ∑i=1n∣Ai−Bi∣\sum\limits_{i = 1}^{n}|A_i-B_i|i=1∑n​∣Ai​−Bi​∣. 输入描述 The first line of input contains two integers N,KN,KN,K (2≤N≤5×1052≤N≤5×10^52≤N≤5×105 ,0≤K≤1080≤K≤10^80≤K≤108), describing the length of AAA, BB ...

Given an extremely large non-negative integer nnn, you are asked to count the number of pairs (i,j)(i,j)(i,j) of integers satisfying the following conditions: 0≤j≤i≤n0\leq j\leq i\leq n0≤j≤i≤n; i ∧ n=ii\ \wedge\ n=ii ∧ n=i; i ∧ j=0i\ \wedge\ j=0i ∧ j=0. Here $\wedge $ represents the bitwise AND operator. For simplicity, the binary representation of nnn will be given. Meanwhile, you only need to output the answer modulo (109+7)(10^9+7)(109+7). Input The first line contains an integer TTT (1≤T≤2 ...

Problem Statement Takahashi became a pastry chef and opened a shop La Confiserie d’ABC to celebrate AtCoder Beginner Contest 100. The shop sells NN kinds of cakes. Each kind of cake has three parameters “beauty”, “tastiness” and “popularity”. The iii-th kind of cake has the beauty of xix_ixi​, the tastiness of yiy_iyi​ and the popularity of ziz_izi​. These values may be zero or negative. Ringo has decided to have MM pieces of cakes here. He will choose the set of cakes as follows: Do not have t ...

给你一个字符串 sss 和一个字符规律 ppp，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符； '*' 匹配零个或多个前面的那一个元素； 所谓匹配，是要涵盖 整个字符串 sss 的，而不是部分字符串。 示例 1 输入：s=s =s="aa" p=p =p= "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。 示例 2 输入：s=s =s= "aa" p=p =p= "a*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。 示例 3 输入：s=s =s= "ab" $p = $".*" 输出：true 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。 示例 4 输入：s=s =s= "aa ...

Problem Description 背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele 也终于要开始背单词了。 一天，Lele 在某本单词书上看到了一个根据词根来背单词的方法。比如 “ab”“ab”“ab”,放在单词前一般表示“相反，变坏，离去"等。 于是Lele想，如果背了 nnn 个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过 lll，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。 比如一共有 222 个词根 “aa”“aa”“aa” 和 “ab”“ab”“ab” ，则可能存在 104104104 个长度不超过 333 的单词，分别为 (2个) aa,abaa,abaa,ab (26个)aaa,aab,aac⋯aazaaa,aab,aac\cdots aazaaa,aab,aac⋯aaz (26个)aba,abb,abc⋯abzaba,abb,abc\cdots abzaba,abb,abc⋯abz (25个)baa,caa,daa⋯zaabaa,caa,daa\cdots z ...

观察这个数列：[1,3,0,2,−1,1,−2⋯ ][1, 3, 0, 2, -1,1, -2 \cdots][1,3,0,2,−1,1,−2⋯]。 这个数列中后一项总是比前一项增加 222 或者减少 333，且每一项都为整数。 栋栋对这种数列很好奇，他想知道长度为 nnn 和为 sss 而且后一项总是比前一项增加 aaa 或者减少 bbb 的整数数列可能有多少种呢？ 输入格式 共一行，包含四个整数 n,s,a,bn,s,a,bn,s,a,b，含义如前面所述。 输出格式 共一行，包含一个整数，表示满足条件的方案数。 由于这个数很大，请输出方案数除以 100000007100000007100000007 的余数。 数据范围 1≤n≤10001≤n≤10001≤n≤1000, −109≤s≤109−10^9≤s≤10^9−109≤s≤109, 1≤a,b≤1061≤a,b≤10^61≤a,b≤106. 输入样例： 14 10 2 3 输出样例： 12 样例解释 两个满足条件的数列分别是 [2,4,1,3][2,4,1,3][2,4,1,3] 和 [7,4,1,−2][7,4,1,-2][ ...

X 国王有一个地宫宝库，是 n×mn×mn×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。 地宫的入口在左上角，出口在右下角。 小明被带到地宫的入口，国王要求他只能向右或向下行走。 走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。 当小明走到出口时，如果他手中的宝贝恰好是 kkk 件，则这些宝贝就可以送给小明。 请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 kkk 件宝贝。 输入格式 第一行 333 个整数，n,m,kn,m,kn,m,k，含义见题目描述。 接下来 nnn 行，每行有 mmm 个整数 CiC_iCi​ 用来描述宝库矩阵每个格子的宝贝价值。 输出格式 输出一个整数，表示正好取 kkk 个宝贝的行动方案数。 该数字可能很大，输出它对 100000000710000000071000000007 取模的结果。 数据范围 1≤n,m≤501≤n,m≤501≤n,m≤50, 1≤k≤121≤k≤121≤k≤12, 0≤Ci≤120≤C_i≤120≤Ci​≤12. 输入样例1： 1232 ...

对于一个字符串 SSS，我们定义 SSS 的分值 f(S)f(S)f(S) 为 SSS 中恰好出现一次的字符个数。 例如 f(“aba”)=1f(“aba”)=1f(“aba”)=1，f(“abc”)=3f(“abc”)=3f(“abc”)=3，f(“aaa”)=0f(“aaa”)=0f(“aaa”)=0。 现在给定一个字符串 S[1⋯n]S[1\cdots n]S[1⋯n]（长度为 nnn），请你计算对于所有 SSS 的非空子串 S[i…j]S[i…j]S[i…j]（1≤i≤j≤n1≤i≤j\le n1≤i≤j≤n），f(S[i…j])f(S[i…j])f(S[i…j]) 的和是多少。 输入格式 输入一行包含一个由小写字母组成的字符串 SSS。 输出格式 输出一个整数表示答案。 数据范围 对于 $20\%$ 的评测用例，1≤n≤101≤n≤101≤n≤10； 对于 $40\%$ 的评测用例，1≤n≤1001≤n≤1001≤n≤100； 对于 $50\%$ 的评测用例，1≤n≤10001≤n≤10001≤n≤1000； 对于 $60\%$ 的评测用例，1≤n≤100001≤n≤1000 ...

xxx 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。各大厂商也就纷纷推出各种耐摔型手机。 xxx 星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。 xxx 星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。 塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的 222 楼。 如果手机从第777 层扔下去没摔坏，但第 888层摔坏了，则手机耐摔指数为 777。 特别地，如果手机从第 111 层扔下去就坏了，则耐摔指数 000。 如果到了塔的最高层第 nnn 层扔没摔坏，则耐摔指数是 nnn。 为了减少测试次数，从每个厂家抽样 333 部手机参加测试。 如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？ 输入格式 一个整数 nnn，表示测试塔的高度。 输出格式 一个整数，表示最多测试多少次。 数据范围 3≤n≤100003≤n≤100003≤n≤10000 输入样例1： 13 输出样例1： 12 样例1解释 手机 aaa 从 222 楼扔下去，坏 ...