亟隐

朝不闻道,夕亦死可矣

09/15
00:02
DP 数学 算法区

HDU 4626 Jinkeloid

地址:戳这里

Problem Description
After listening several songs of Jinkeloid,I come up with this problem :).
There is a string s only consist of first 20 lowercase English letters.
And we have several queries,each time I have k letters c1, c2, …, ck,and I wonder how many consecutive substring of string s that each ci has occur even times in it.
Two substring with the same content but different position are considered different.

Read More →

09/8
15:39
数学 算法区

BZOJ 3930 [CQOI2015]选数

地址:戳这里

Description

 我们知道,从区间[L,H](L和H为整数)中选取N个整数,总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的N个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。你的任务很简单,小z会告诉你一个整数K,你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大,你只需要输出其除以1000000007的余数即可。

Read More →

02/7
14:12
数学 算法区

SPOJ 8277 Number of Prime Strings Mobius

地址:戳这里

A string is called a “prime string” if it can’t be written as concatenation of more than one same strings. For example, the following strings are not prime strings: AAA, ABABAB, CFGFGCFGFG, while CFGFGC, ABABA are prime strings.
Calculate the number of prime string of length N (1<=N<=1000000), and only contains first K (1<=K<=26) letters from English alphabet. Note that some of these K letters need not appear in that string. Read More →

02/2
12:17
数学 算法区

HDU 4675 GCD of Sequence 容斥

地址:戳这里

Problem Description
Alice is playing a game with Bob.
Alice shows N integers a1, a2, …, aN, and M, K. She says each integers 1 ≤ ai ≤ M.
And now Alice wants to ask for each d = 1 to M, how many different sequences b1, b2, …, bN. which satisfies :
1. For each i = 1…N, 1 ≤ b[i] ≤ M
2. gcd(b1, b2, …, bN) = d
3. There will be exactly K position i that ai != bi (1 ≤ i ≤ n) Read More →

01/30
11:30
数学 算法区

BZOJ 2005 [Noi2010]能量采集 莫比乌斯反演

地址:戳这里

Description

栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐,一共有n列,每列有m棵,植物的横竖间距都一样,因此对于每一棵植物,栋栋可以用一个坐标(x, y)来表示,其中x的范围是1至n,表示是在第x列,y的范围是1至m,表示是在第x列的第y棵。 由于能量汇集机器较大,不便移动,栋栋将它放在了一个角上,坐标正好是(0, 0)。 Read More →

01/28
19:28
数学 算法区

SPOJ 4491 Primes in GCD Table 莫比乌斯反演

地址:戳这里

Johnny has created a table which encodes the results of some operation — a function of two arguments. But instead of a boring multiplication table of the sort you learn by heart at prep-school, he has created a GCD (greatest common divisor) table! So he now has a table (of height a and width b), indexed from (1,1) to (a,b), and with the value of field (i,j) equal to gcd(i,j). He wants to know how many times he has used prime numbers when writing the table. Read More →