给定一个长度为 $$$n$$$ 的数组 $$$a$$$, 第 $$$i$$$ 个元素 为 $$$a_i$$$, 定义 $$$gcd(l ,r)$$$ 为 $$$a$$$ 数组中下标在 $$$[l, r]$$$ 中的所有数的最大公约数, $$$sum(l, r)$$$ 为 在 $$$a$$$ 数组中下标在 $$$[l, r]$$$ 中的所有数的和。
你要找到满足 $$$gcd(l, r) \le sum(l, r)$$$ 的所有区间的个数。
第一行有一个正整数 $$$n~ (n \le 10^5)$$$ ,第二行有 $$$n$$$ 个正整数, $$$a_i~(a_i \le 10^9)$$$ 。
输出一个整数,表示满足条件的区间个数。
3 1 1 2
3
定义一个长度为$$$n$$$的数组 $$$a_1,a_2,\cdots,a_n$$$ 是好数组当且仅当 $$$\forall{i}\in[1,n),~a_1~|~a_2|~\cdots~|a_i~=~a_{i+1}~|~\cdots~|~a_n$$$。其中$$$|$$$表示按位或运算。
小文有一个长度为$$$n$$$的数组 $$$a_1,a_2,\cdots,a_n$$$,他想知道有多少个不同的$$$1$$$到$$$n$$$的排列 $$$p_1,p_2,\cdots,p_n$$$,使得 $$$a_{p_1},a_{p_2},\cdots,a_{p_n}$$$ 是一个好数组。
满足条件的排列数量可能会很大,你只需要输出其对 $$$998244353$$$ 取模后的结果即可。
第一行输入一个整数 $$$t~(1\leq{t}\leq{10^5})$$$ 表示有$$$t$$$组样例。
每一个样例的第一行输入一个整数$$$n~(2\leq{n}\leq{2\cdot{10^5}})$$$。
每一个样例的第二行输入$$$n$$$个整数 $$$a_1,a_2,\cdots,~a_n(1\leq{a_i} \lt 2^{30})$$$。
数据保证所有样例的$$$n$$$之和不超过 $$$2\cdot{10^5}$$$。
对于每个样例输出一个整数,即满足条件的排列数对 $$$998244353$$$ 取模后的结果。
4 2 1 1 3 1 2 3 5 1 3 2 2 3 4 1000000000 5454135 1000000000 9985453
2 0 12 0
你有$$$n$$$种砝码,第$$$i$$$种砝码重量为$$$a_i$$$,每种砝码有无限个。你有一架秤,你只能在同一边放上砝码,现在你想这架秤能称出$$$1\sim m$$$所有的重量,请问最少需要多少个砝码?
比如,有$$$3$$$种砝码,重量分别为$$$1,2,4$$$,你需要称出$$$1\sim 8$$$的重量,你最少需要$$$4$$$个砝码。
第一行输入一个整数$$$T~(1 \le T \le 50)$$$,表示样例的个数。
每个样例的第一行是两个整数$$$n~(1 \le n \le 10000),~m~(1 \le m \le 10^9)$$$,分别表示砝码的种类,与需要称出重量的右边界。
第二行是$$$n$$$种砝码的重量,砝码按重量从小到大给出,任意两个砝码重量不相同,重量处于$$$[1,100000]$$$。
依次每行输出一个样例的结果,为一个整数。如果不可能达到目标,输出$$$-1$$$。
3 3 8 1 2 4 3 4 2 3 4 3 4 1 2 3
4 -1 3
一个长度为$$$n$$$的仅包含小写字母的字符串,你需要找到两个不相交的非空子串,保证子串中的各字母出现次数均不超过$$$m$$$,求两个子串长度之和的最大值。
其中子串是指对于字符串$$$S=s_1~s_2~\cdots~s_n$$$,取一个区间$$$[l,r],~l \le r$$$,字符串 $$$s_l~s_{l+1}~\cdots~s_r$$$ 叫做字符串$$$S$$$的子串。
子串不相交是指这两个子串没有重叠的部分。
第一行是一个正整数 $$$T~(1\le T\le 10^3)$$$,表示样例组数,以后是$$$T$$$组样例的输入。
对于每组样例:
第一行包含两个正整数 $$$n~(2 \le n \le 10^6)$$$ 和 $$$m~(1 \le m \le n)$$$;第二行是一个长度为$$$n$$$的仅包含小写字母的字符串。
输入保证 $$$\sum n \le 10^6$$$。
依次输出每组样例的结果,为一行,仅包含一个整数,表示答案。
3 2 1 ab 5 1 ababa 10 2 ababababab
2 4 8
给定两个长度为$$$n$$$的整数序列$$$a$$$,$$$b$$$。你可以最多一次翻转序列$$$a$$$的一个区间,最小化$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}$$$。
所谓翻转区间$$$[l,r]$$$,就是$$$a=\{a_1,~a_2,~\ldots,~a_l,~\ldots,a_r,~\ldots,~a_n\}$$$,翻转以后变为$$$a_1,~a_2,~\ldots,~a_r,~a_{r-1},~\ldots,~a_{l+1},~a_l,~\ldots,~a_n$$$。
表达式 $$$x\oplus{y}$$$表示对$$$x$$$与$$$y$$$二进制表示下按位异或的结果。
第一行输入单个整数 $$$n(1\leq{n}\leq{5000})$$$。
第二行输入$$$n$$$个整数 $$$a_1,a_2,\cdots,a_n$$$,代表序列 $$$a,~(1\leq{a_i}\leq{10^9})$$$。
第三行输入$$$n$$$个整数 $$$b_1,b_2,\cdots,b_n$$$,代表序列 $$$b,~(1\leq{b_i}\leq{10^9})$$$。
输出一个整数,表示$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}$$$的最小值。
5 1 2 3 4 5 1 4 3 2 5
0
5 3 6 9 1 6 5 2 6 2 2
20
3 15 84 28 29 44 94
76
10 13 71 26 93 100 78 80 90 42 62 37 6 78 32 33 57 84 71 2 53
416
样例$$$1$$$选择反转区间 $$$[2,4]$$$ 后,序列$$$a$$$变为 $$$1,4,3,2,5$$$ 。此时$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}=0$$$,显然这个是最小的。
样例$$$2$$$选择反转区间 $$$[1,4]$$$ 后,序列$$$a$$$变为 $$$1,9,6,3,6$$$ 。此时$$$\sum_{i=1}^{n}{a_i\oplus{b_i}}=20$$$,可以证明这样操作是最优的。
LOL游戏中有五个不同的位置,分为上单,打野,中单,ADC和辅助,每个位置必须有一位选手,一位选手也只能玩一个位置。
夏季赛要开始了,你作为战队经理,要安排首发阵容。但是,战队里的队员实在太多了,而且每个人能打的位置也不相同,你想知道一共有多少种不同的阵容组合。
不同的阵容是指相同位置上的队员如果不同,就认为是不同的阵容。
输入一个整数$$$n~(5 \le n \le 2\cdot 10^5)$$$,表示战队的人数。
接下来$$$n$$$行每行为长度$$$5$$$的$$$01$$$串。其中,$$$1$$$表示队员可以打这个位置,$$$0$$$则相反。
输出一个整数,表示阵容组合的方案数,由于这个答案可能很大,请将其对$$$10^9+7$$$取模。
5 10000 01000 00100 00010 00001
1
6 10000 01000 00001 00010 00100 00001
2
对于样例一,共有$$$5$$$个人,他们正好每个人只能去一个位置,所以只有一套首发;
对于样例二,$$$3$$$号和$$$6$$$号队员正好都可以打位置$$$5$$$,所以有两套首发。