[TOC]

hankin练习1

// 坑点：组合里面也应要有顺序组合---单独的aeio应该是1
// 比如aeio组合，在算任意两个数绑在一起的时候不能把io放在一起
// 搞不懂为何错了，啊啊啊啊啊
#include <iostream>
#include <string>
#define LL long long
using namespace std;

const char specil[] = { 'a', 'e', 'i', 'o' };

LL factorial(int n)
{
    LL ret = 1;
    for (int i = 2; i <= n; i++) {
        ret *= i;
    }
    return ret;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        int len = str.size();
        if (1 == len) {
            cout << 1 << endl;
            continue;
        }
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 4; j++) {
                if (str[i] == specil[j]) {
                    cnt++;
                }
            }
        }

        LL all_combine = factorial(len);
        if (2 == cnt) {
            all_combine -= factorial(len - 1) * factorial(2);
        }
        else if (3 == cnt) {
            all_combine -= factorial(len - 1) * 3 * factorial(2);
            all_combine += factorial(len - 2) * factorial(3);
        }
        else if (4 == cnt) {
            all_combine -= factorial(len - 2) * (len - 1) * 6 * factorial(2);
            all_combine += factorial(len - 3) * (len - 2) * 4 * factorial(3);
            all_combine -= factorial(len - 4) * (len - 3) * factorial(4);
            //all_combine -= factorial(len - 1) * 6 * factorial(2);   没有区别，真的有点搞笑，跑了一圈尖山湖想出来的
            //all_combine += factorial(len - 2) * 4 * factorial(3);
            //all_combine -= factorial(len - 3) * factorial(4);
        }
        cout << all_combine << endl;
    }
    return 0;
}

正解

#include <iostream>
#include <string>
#define LL long long
using namespace std;

const char specil[] = { 'a', 'e', 'i', 'o' };

LL factorial(int n)
{
    LL ret = 1;
    for (int i = 2; i <= n; i++) {
        ret *= i;
    }
    return ret;
}

LL C[105][105];
void combine()
{
    for (int i = 1; i < 105; i++) {
        C[i][0] = 1;
        C[i][1] = i;
        C[i][i] = 1;
        for (int j = 2; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        int len = str.size();
        if (1 == len) {
            cout << 1 << endl;
            continue;
        }
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 4; j++) {
                if (str[i] == specil[j]) {
                    cnt++;
                }
            }
        }
        combine();
        int common = len - cnt;
        LL all_combine = factorial(common) * C[common + 1][cnt] * factorial(cnt);
        cout << all_combine << endl;
    }
    return 0;
}

排除

// 坑点：组合里面也应要有顺序组合---单独的aeio应该是1
// 比如aeio组合，在算任意两个数绑在一起的时候不能把io放在一起
// 搞不懂为何错了，啊啊啊啊啊
#include <iostream>
#include <string>
#define LL long long
using namespace std;

const char specil[] = { 'a', 'e', 'i', 'o' };

LL A(int n)
{
    LL ret = 1;
    for (int i = 2; i <= n; i++) {
        ret *= i;
    }
    return ret;
}

LL C[105][105];
void combine()
{
    for (int i = 1; i < 105; i++) {
        C[i][0] = 1;
        C[i][1] = i;
        C[i][i] = 1;
        for (int j = 2; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        int len = str.size();
        if (1 == len) {
            cout << 1 << endl;
            continue;
        }
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 4; j++) {
                if (str[i] == specil[j]) {
                    cnt++;
                }
            }
        }

        combine();
        LL ans = A(len);
        for (int i = 2; i <= cnt; i++) {  //不能排除其他元素不能在一起，否则还需要后面的加减干嘛。。。
            if (i & 1) {
                ans += A(len - cnt) * C[len - cnt + 1][cnt - i + 1] * C[cnt][i] * A(i);
            }
            else {
                ans -= A(len - cnt) * C[len - cnt + 1][cnt - i + 1] * C[cnt][i] * A(i);
            }
        }
        cout << ans << endl;
    }
    return 0;
}