yukicoder 169/170/171

hugo 製ブログ初の解説記事は yukicoder です。 タグと syntax highlight の機能は後で入れます＞＜

169 : 何分かかるの！？

問題文

算数です。

int main(){
    ll K,S;
    cin >> K >> S;
    cout << S * 100/(100-K) << endl;
}

170,171 : スワップ文字列

問題文 : Easy, Med

Easy と Med をまとめます。

swap だけで任意の順列が作れるので、含まれる文字からなる順列を数えます。ただ、$mod$ が素数じゃないので工夫が必要で、 $n! / (a!b!c!d!) = C(n,a) C(n-a,b) C(n-a-b,c) C(n-a-b-c,d) $ のように変形すると割り算がいらなくなります。(この方法高校で習った気がする) 二項係数 $C(n,r)$ はパスカルの三角形で求めます。

最後に1引くときに負の数にしてしまって 2WA 食らいました。 あと多倍長ずるい。

ll const mod = 1<<29; /* med の場合は 573 */

const int MAX_N = 10000; //400MB
// const int MAX_N = 1024; // 4MB
// nCr % mod
ll nCr(int n, int r){
    static bool done[MAX_N+1][MAX_N/2+2];
    static ll dp[MAX_N+1][MAX_N/2+2]; // 400MB
    if (n < 0 || r < 0 || n < r) return 0;
    if (r==0) return 1;
    if (r > n-r) r = n-r;
    ll &res = dp[n][r];
    if (done[n][r]) return res;
    done[n][r] = true;
    return res = (nCr(n-1,r-1)+nCr(n-1,r)) % mod;
}

int main(){
    string s;
    cin >> s;
    map<char,ll> m;
    for(char c:s) m[c]++;
    ll ans = 1;
    ll rem = s.size();
    for(auto & p : m){
        ans *= nCr(rem, p.second);
        ans %= mod;
        rem -= p.second;
    }
    ans += mod-1;
    ans %= mod;
    cout << ans << endl;
}