SRM586 Div2 Hard "StringWeightDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12695

訳

この問題では、全ての文字列は大文字のアルファベットでしか構成されないとする。つまり、26種類の文字しかない。

文字列 S の重さは次のように計算される。Sに１つでもあるそれぞれの文字で、その最も左の位置をL、最も右の位置をRとすると、重さはR-Lだけ増加する。

例えば、S="ABCACAX"であれば、Sの重さは(5-0) + (1-1) + (4-2) + (6-6) = 7となる。（'A'の最も左の位置は0であり、最も右の位置は5であるため、'A'で重さは5-0=5だけ増加している。Bは0、Cは2、Zは0だけ重さを増加させている）

あなたはint Lが与えられる。全ての長さLの文字列を考える。これらの文字列の重さを計算する。この中で、最も重さが少ない文字列を"lightである"とする。長さLのlightな文字列はいくつあるかを返せ。

制約

1 <= L <= 1000

考えた事

Lが26以下であるならば、各文字を１つずつしか使わないことにより、重さを0に出来る。よって例えばL=5であれば、26 * 25 * 24 * 23 * 22通りのlightな文字列ができる。

Lが27以上であるならば、各文字を１つ以上使い、１種類の文字はくっつけた時にlightな文字列が出来上がる（当社調べ）。簡単のため文字の種類が'ABC'しかなくて、L=7であるとする。lightな文字列は以下のようなものである。

AABBBCC
AAAAABC
BBBACCC
CAAAAAB
などなど...

とあるニコ生にて

これはL-1の場所に、25個の仕切りをどのように配置するか？という問題になる。

よって答えは(L-1)_C_25となる。

ただし、これは文字をABC...Zと順に置いた場合の数になる。文字の順番は好きに選べるので、26 * 25 * ... * 1の26!をかけてあげればよい。よって答えは(L-1)_C_25 * 26!となる。

ソースコード

const int MOD = 1000000009;

class StringWeightDiv2 {
public:

    int countMinimums(int L){
        long long ans = 1;

        if( L <= 26 ){
            for( int i = 0; i < L; i++ ){
                ans = ans * (26 - i) % MOD;
            }
        }else{
            for( int i = L - 1; i >= L - 25; i-- ){
                ans = ans * i % MOD;
            }
            ans = ans * 26 % MOD;
        }
        return (int)ans;
    }
};