V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
牛客网
lihongming
V2EX  ›  程序员

脑子突然不好使了,请各位大佬帮我想想这个算法

  •  
  •   lihongming · 46 天前 · 3394 次点击
    这是一个创建于 46 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已知有一个长度为 26 的整型数组,分别代表 26 个字母的个数,问这些字母能组成多少种不同的字符串(取模 1000000007 )。

    我本来觉得挺简单,不就是迭代吗?抬手就来

    int calc(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                nums[i]--;
                ret += calc(nums);
                ret %= 1000000007;
                nums[i]++;
            }
        }
        return ret > 0 ? ret : 1;
    }
    

    结果效率太差,不行。

    我又想用数学的方法直接算,可脑子怎么也想不起该怎么算了,求大佬们指点。

    22 条回复    2020-09-08 18:30:09 +08:00
    xuanbg
        1
    xuanbg   46 天前   ❤️ 1
    2^32^26
    lihongming
        2
    lihongming   46 天前   ❤️ 1
    想起来了,应该是各数之和的阶乘除以各数的阶乘
    (A + B + C + ...)! / (A! * B! * C! * ...)
    git00ll
        3
    git00ll   46 天前
    楼主这题哪里做的,能发下链接吗
    lff0305
        4
    lff0305   46 天前
    数学方式直接算:应该是指数生成函数
    crackhopper
        5
    crackhopper   46 天前
    进一步优化,还需要找到 k!>i*1000000007 的对可以每个出现的 i,最小的 k 。可以快速简化计算。
    crackhopper
        6
    crackhopper   46 天前
    刚才没考虑,还有除数,比较麻烦。当我之前没说
    flowfire
        7
    flowfire   46 天前   ❤️ 1
    这不是排列组合吗。。。
    答案是(假设 a-z 分别代表各个字母的数量,大写 S 代表所有字母总数):
    A(S,S) / (A(a,a) * A(b,b) * ...... * A(z,z))
    flowfire
        8
    flowfire   46 天前
    guonaihong
        9
    guonaihong   46 天前
    对这个问题感兴趣。这些字母是否是互斥事件吗?比如第一位是 26 种可能,互斥的话,第二种是 25 种可能。
    我的理解,根据条件有 2 种解 一种,26 * 26 ....n,即 26 的 26 次方。二种是后者就是 26!。
    如果是组合的话,就是把重复计算的除掉 m 种取 n 种 =m!/(m-n)!n!。
    lff0305
        10
    lff0305   46 天前
    简单写了个程序。题目没有讲太清楚(是否这些字母一定要全部使用)。这里为了简单就假设全部使用。

    解法一:排列组合。生成字符串长度是 sum=a0+a1+a2+...+a25 。放 a,有(sum, a0)种选择的方法;放 b,有(sum - a0, a1)种方法;放 c,有(sum - a0 - a1, a2)种方法。。。。直到最后。

    写出程序:

    private long solve1(int[] letters) {
    int sum = 0;
    for (int c : letters) {
    sum += c;
    }
    BigInteger r = BigInteger.ONE;
    for (int c : letters) {
    BigInteger s = choose(sum, c);
    r = r.multiply(s);
    sum -= c;
    }
    return r.longValue();
    }

    private static BigInteger choose(int n, int k) {
    BigInteger r = BigInteger.ONE;
    for (int i=0; i<k; i++) {
    r = r.multiply(BigInteger.valueOf(n - i));
    }
    for (int i=2; i<=k; i++) {
    r = r.divide(BigInteger.valueOf(i));
    }

    // System.out.println(n + "," + k + " = " + r);
    return r;
    }


    解法 2: GEF (指数生成函数)。这是个排列问题所以用指数生成函数。
    对于 a: 有 a0 个 a 要放。写成指数函数形式 e0=e^(a0)/a0!
    同样对于 b: 有 a1 个 b 要放。写成指数函数形式 e1=e^(a1)/a1!
    等等等等
    最后到 z, 有 a25 个 z 要放,写成指数函数形式 e25=e^(a25)/a5!

    根据指数生成函数的理论,整个排列数就是
    E=e0*e1*...*e25,中项 e^(sum)/sum! 的系数。

    那么 E=[e^(a0)/a0!][e^(a1)/a1!]*...*[e25=e^(a25)/a25!]
    = [e^(a0+a1+...+a25)]/[a0!*a1!*...*a25!]
    = [e^sum]/[a0!*a1!*...*a25!]
    e ^ sum sum !
    = --------------------------- * --------------------
    a0! *a1!* ... * a25 !) sum!

    e ^ sum sum !
    = --------------------------- * --------------------------
    sum! a0! *a1!* ... * a25 !

    要求的系数就是 ( sum!)/( a0! *a1!* ... * a25 ! )

    写成程序就是


    // Solve by GEF
    private long solve2(int[] a) {
    // expr e0 = e^a0/a0!, e1 = e^a1/a1! ... etc
    // E = e0*e1*e2 .... * e25
    // e^(a0+a1+...+a25)/(a0!*a1*a2*....*a25!)
    // ? = e^(a0 + a1 + ... + a25)/(sum!)
    int sum = 0;
    for (int c : a) {
    sum += c;
    }
    BigInteger p = p(sum);
    BigInteger c = BigInteger.ONE;
    for (int i : a) {
    c = c.multiply(p(i));
    }
    return p.divide(c).longValue();
    }

    private BigInteger p(int sum) {
    BigInteger r = BigInteger.ONE;
    for (int i= sum; i>=2; i--) {
    r = r.multiply(BigInteger.valueOf(i));
    }
    return r;
    }
    lff0305
        11
    lff0305   46 天前
    排版乱了, 重新弄下

    简单写了个程序。题目没有讲太清楚(是否这些字母一定要全部使用)。这里为了简单就假设全部使用。

    解法一:排列组合。生成字符串长度是 sum=a0+a1+a2+...+a25 。放 a,有(sum, a0)种选择的方法;放 b,有(sum - a0, a1)种方法;放 c,有(sum - a0 - a1, a2)种方法。。。。直到最后。

    写出程序:
    ```
    private long solve1(int[] letters) {
    int sum = 0;
    for (int c : letters) {
    sum += c;
    }
    BigInteger r = BigInteger.ONE;
    for (int c : letters) {
    BigInteger s = choose(sum, c);
    r = r.multiply(s);
    sum -= c;
    }
    return r.longValue();
    }

    private static BigInteger choose(int n, int k) {
    BigInteger r = BigInteger.ONE;
    for (int i=0; i<k; i++) {
    r = r.multiply(BigInteger.valueOf(n - i));
    }
    for (int i=2; i<=k; i++) {
    r = r.divide(BigInteger.valueOf(i));
    }

    // System.out.println(n + "," + k + " = " + r);
    return r;
    }

    ```
    解法 2: GEF (指数生成函数)。这是个排列问题所以用指数生成函数。
    对于 a: 有 a0 个 a 要放。写成指数函数形式 e0=e^(a0)/a0!
    同样对于 b: 有 a1 个 b 要放。写成指数函数形式 e1=e^(a1)/a1!
    等等等等
    最后到 z, 有 a25 个 z 要放,写成指数函数形式 e25=e^(a25)/a5!

    根据指数生成函数的理论,整个排列数就是
    E=e0*e1*...*e25,中项 e^(sum)/sum! 的系数。

    那么
    ```
    E=[e^(a0)/a0!][e^(a1)/a1!]*...*[e25=e^(a25)/a25!]
    = [e^(a0+a1+...+a25)]/[a0!*a1!*...*a25!]
    = [e^sum]/[a0!*a1!*...*a25!]
    e ^ sum sum !
    = --------------------------- * --------------------
    a0! *a1!* ... * a25 !) sum!

    e ^ sum sum !
    = --------------------------- * --------------------------
    sum! a0! *a1!* ... * a25 !
    ```
    要求的系数就是 ( sum!)/( a0! *a1!* ... * a25 ! )

    写成程序就是

    ```
    // Solve by GEF
    private long solve2(int[] a) {
    // expr e0 = e^a0/a0!, e1 = e^a1/a1! ... etc
    // E = e0*e1*e2 .... * e25
    // e^(a0+a1+...+a25)/(a0!*a1*a2*....*a25!)
    // ? = e^(a0 + a1 + ... + a25)/(sum!)
    int sum = 0;
    for (int c : a) {
    sum += c;
    }
    BigInteger p = p(sum);
    BigInteger c = BigInteger.ONE;
    for (int i : a) {
    c = c.multiply(p(i));
    }
    return p.divide(c).longValue();
    }

    private BigInteger p(int sum) {
    BigInteger r = BigInteger.ONE;
    for (int i= sum; i>=2; i--) {
    r = r.multiply(BigInteger.valueOf(i));
    }
    return r;
    }
    ```
    QingchuanZhang
        12
    QingchuanZhang   46 天前
    @lff0305 EGF 。。。
    lihongming
        13
    lihongming   46 天前 via iPhone
    @guonaihong 是的,要全用上。比如给你 2 个 a 和 2 个 b,那么能组成 aabb, abab, abba, baab, baba, bbaa 六种字符串
    waruqi
        14
    waruqi   46 天前 via Android
    不就是 26 进制的 26 位数累加迭代么,直接用个 uint64 累加遍历么,然后将每个 10 进制数转成 26 进制,按每位映射到对应字母就好了,迭代到 26 位后结束,uint64 不够 就换 uint128 uint256
    toaruScar
        15
    toaruScar   46 天前
    难道这个不是基础的 permutations with pepetitions 吗?
    no1xsyzy
        16
    no1xsyzy   45 天前
    @lihongming @flowfire @lff0305 @toaruScar 问题是,整除是不是模数空间上的群?
    当然,拿 BigInt 之类做归做,效率是问题。

    @waruqi uint32 遍历需要大约 42 秒
    uint64 已经要遍历到天荒地老。
    怎么会想到遍历的,服(
    no1xsyzy
        17
    no1xsyzy   45 天前
    简单重排一下的话
    (A + B + C + ...)! / (A! * B! * C! * ...)
    其实等于
    A!/A! * ((A+B)!/A!/B!) * ((A+B+C)!/(A+B)!/C!) * ...
    每块都是整数。
    flowfire
        18
    flowfire   45 天前
    @no1xsyzy #17 你这算法跟我的不一样吗。。。无非是表达方法不同罢了。。。

    A(m,m) 就是 m! 啊。。。。
    toaruScar
        19
    toaruScar   45 天前 via iPhone
    @flowfire #18 @no1xsyzy 的意思是,题目最后一步要求 mod,那不如就直接在 mod 的空间里计算。就是每步运算之后都去来个 mod,这样数字能小一点。然而 mod 空间里只有加减乘能用,也就是
    ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
    ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
    ( a – b) % c = ( ( a % c ) – ( b % c ) ) % c
    而( a / b) % c 是没有这个性质的
    重排一下发现可以相消,于是分母都是 1,也就是只剩下乘法了。
    no1xsyzy
        20
    no1xsyzy   45 天前
    刚地铁上突然意识到一点,整除有可能是模数空间上的群,因为给定整除,采用启发式算法的话,可能可行……
    等我稍微写写 test 一下
    no1xsyzy
        21
    no1xsyzy   45 天前
    竟然是可以的…… 之前拍脑袋了
    已知整除的话,整除是模数空间上的群……
    那没关系了,用模数空间上的整除做就行了。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2783 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 03:36 · PVG 11:36 · LAX 20:36 · JFK 23:36
    ♥ Do have faith in what you're doing.