0028.子序列中的k种字母.md

28.子序列中的 k 种字母

题目链接

C++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int res = 0;

void dfs(int* cnt, int k, char* chars, int charsSize, int index, char* path, int pathSize) {
    if (k == pathSize) {
        long long tmp = 1LL;
        for (int i = 0; i < pathSize; ++i) {
            tmp *= ((long long)pow(2, cnt[path[i] - 'a']) - 1) % ((long long)pow(10, 9) + 7);
        }
        res += (int)(tmp % ((long long)pow(10, 9) + 7));
        return;
    }
    for (int i = index; i < charsSize; ++i) {
        path[pathSize] = chars[i];
        dfs(cnt, k, chars, charsSize, i + 1, path, pathSize + 1);
    }
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    char s[1001];
    scanf("%s", s);
    int cnt[26] = {0};
    int cntSize = 26;
    for (int i = 0; s[i] != '\0'; ++i) {
        cnt[s[i] - 'a']++;
    }

    char chars[cntSize];
    int charsSize = 0;
    for (int i = 0; i < cntSize; ++i) {
        if (cnt[i] > 0) {
            chars[charsSize++] = 'a' + i;
        }
    }

    char path[k];
    dfs(cnt, k, chars, charsSize, 0, path, 0);
    printf("%d\n", res);

    return 0;
} 

Java

import java.util.*;

public class Main {
    private static int res = 0;
    private static final int MOD = 1000000007; // (10^9 + 7)

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        int[] cnt = new int[26];
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
            set.add(c);
        }
        List<Character> chars = new ArrayList<>(set);
        dfs(cnt, k, chars, 0, new ArrayList<Character>());
        System.out.println(res);
    }

    private static void dfs(int[] cnt, int k, List<Character> chars,
                            int index, List<Character> path) {
        if (k == path.size()) {
            long tmp = 1;
            for (char c : path) {
                tmp = (tmp * (powerMod(2, cnt[c - 'a'], MOD) - 1)) % MOD;
            }
            res = (int) ((res + tmp) % MOD);
            return;
        }
        for (int i = index; i < chars.size(); i++) {
            path.add(chars.get(i));
            dfs(cnt, k, chars, i + 1, path);
            path.remove(path.size() - 1);
        }
    }

    private static long powerMod(long base, int exponent, int modulus) {
        long result = 1;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % modulus;
            }
            base = (base * base) % modulus;
            exponent /= 2;
        }
        return result;
    }
}

Python

Go

Js

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int res = 0;

void dfs(int* cnt, int k, char* chars, int charsSize, int index, char* path, int pathSize) {
    if (k == pathSize) {
        long long tmp = 1LL;
        for (int i = 0; i < pathSize; ++i) {
            tmp *= ((long long)pow(2, cnt[path[i] - 'a']) - 1) % ((long long)pow(10, 9) + 7);
        }
        res += (int)(tmp % ((long long)pow(10, 9) + 7));
        return;
    }
    for (int i = index; i < charsSize; ++i) {
        path[pathSize] = chars[i];
        dfs(cnt, k, chars, charsSize, i + 1, path, pathSize + 1);
    }
}
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    char s[1001];
    scanf("%s", s);
    int cnt[26] = {0};
    int cntSize = 26;
    for (int i = 0; s[i] != '\0'; ++i) {
        cnt[s[i] - 'a']++;
    }
    char chars[cntSize];
    int charsSize = 0;
    for (int i = 0; i < cntSize; ++i) {
        if (cnt[i] > 0) {
            chars[charsSize++] = 'a' + i;
        }
    }

    char path[k];
    dfs(cnt, k, chars, charsSize, 0, path, 0);
    printf("%d\n", res);
    
    return 0;
}