某島

… : "…アッカリ~ン . .. . " .. .
February 16, 2013

Codeforces Round #166

Problem A. Beautiful Year

Brief description:

求比 x 大的第一個不含重複數字的四位數。

Problem B. Prime Matrix

Brief description:

給個 500 * 500 的矩陣,每次操作是可以把一個格子 + 1,最後要求有一行或者一列都是質數就可以。(每個數 < 1e5... (PS:如果改成一次把一行或者一列 + 1 。。。怎麼做?。。

Problem C. Secret

Brief description:

1~n 分成 k 份,使得 k 份都不是等差數列。。
(。。1-k 1-k k-1 1 1 1 1 1 1 1 。。。)

Problem D. Good Substrings

Brief description:

。。給定一個長度為 n 字元串。。每個字元有 好/壞 兩種屬性。。( n <= 1,500 一個字串被稱為好的。。如果其中壞字元 <= k 個。。問不同的好子串有多少個。。 太可怕了…… 卡掉字典序hash的方法 by xhr

Problem E. Three Horses

Brief description:

。三種操作。。

  • (a, b) -> (a+1, b+1) | 平移。。
  • (a, b) -> (a/2, b/2) | 折半。。a, b is even
  • (a, b), (b, c) -> (a, c) | 連接。。

。。問有多少初始操作 (a, b),滿足 1 <= a < b <= m,使得可以通過上述操作生成。。 。。(1, a1), (1, a2), ..., (1, an) 這些二元組。。

Analysis:

考察操作前後的不變數。。操作 1 不改變差值。。
操作二前後差值 /2。。操作三差值支持相加。。

。。因此若只有 a1 時。。設 x = a1 -1 。。
則所有可以生成 x 的 d。。為 x 的所有約數的 2 的整次冪的倍數。。
。。枚舉每個約數。。累計 f(x) 即可。。

LL f(int x){
    if (!(x&1)) return 0;
    LL res = 0; for (int i=0;x<<i<m;++i) res += m-(x<<i);
    return res;
}

。。多個 ai 。。。則開始需要對他們取 gcd 。。。

//}/* .................................................................................................................................. */

int n, m;

LL f(int x){
    if (!(x&1)) return 0;
    LL res = 0; for (int i=0;x<<i<m;++i) res += m-(x<<i);
    return res;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, m); int d = 0; REP(i, n) d = __gcd(d, int(RD()-1));
    int t = sqrt(d); LL res = t*t == d ? -f(t) : 0;
    REP_1(i, t) if (d%i==0) res += f(i) + f(d/i);

	OT(res);
}

External link:

http://codeforces.com/contest/271