数学吧 关注:937,742贴子:8,952,565
  • 20回复贴,共1

一道自己想的排列组合题

只看楼主收藏回复

给定总分x(0<=x<=750),问语数外综合四门课,有多少种可以达到总分x的得分方式。
例如,x = 0时,只有1种,四门都是0分;x = 1时,就有4种,即四门课里选1门得1分;x = 750时,也只有1种,即四门课均为满分。
语数外的满分是150分,综合满分300分。
我自己只会用计算机编程来暴力遍历,时间复杂度O(n^3) 数学吧有没有大神能想到数学的方法啊


IP属地:陕西1楼2024-01-24 23:17回复
    自己顶~我是过从x = 0一直加到x = 750,结果是居然有10多亿种得分方式的总和,也就是得有10多亿个考生,才能把从0分到750分的得分方式全部占满


    IP属地:陕西2楼2024-01-24 23:31
    回复
      2026-03-02 12:32:08
      广告
      不感兴趣
      开通SVIP免广告
      自己顶


      IP属地:陕西来自Android客户端3楼2024-01-25 08:00
      回复
        没有人吗


        IP属地:陕西来自Android客户端4楼2024-01-25 14:36
        回复
          x+y+z+w/2=…,整数解求解问题,隔板法,但会更麻烦


          IP属地:北京来自iPhone客户端5楼2024-01-25 18:05
          收起回复
            别问,问就是母函数
            考虑多项式f(x)=(x^151-1)^3*(x^301-1)/(x-1)^4的各项系数,但是我懒得算


            IP属地:北京来自Android客户端6楼2024-01-25 20:57
            收起回复
              想了半天,发现自己想的思路的本质就是遍历


              IP属地:辽宁来自Android客户端7楼2024-01-26 10:10
              收起回复
                插入法
                将总分数记为x个格子,相当在其中插入3个隔板,每个间隔最小为0,最大为150


                IP属地:湖北来自Android客户端8楼2024-01-26 10:58
                回复
                  2026-03-02 12:26:08
                  广告
                  不感兴趣
                  开通SVIP免广告
                  转换成 纯数学问题 a,b,c 都在【0,150】之间 d 【0,300】 要求a+b+c+d =K
                  求[a,b,c,d]的组合的个数Ans[k]
                  一般而言 计算机计算 是用生成函数思想
                  a在(0~150) 也就是是 (1+x+x^2+...+x^150) 一共4个这样的
                  (1+x+x^2+...+x^150) 在分解因式 可以化简成(x^151-1)/(x-1)
                  (1+x+x^2+...+x^150)^3*(1+x+x^2+...+x^300)
                  最后 和上面6楼一样 但是 很多都是理论 几乎也不好计算出结果
                  如果要算出具体的值 需要用容斥原理
                  需要用到的结论
                  设S是有K种类型对象的多重集合,每种元素均有无限的重复树。那么S的r组合数的个数等于
                  C(r+k-1,r)=C(r+k-1,k-1)
                  解释这个结论 同理这个问题 假设每科满分无上限 要求 总分600分的个数
                  r=600,k=4 结果=C(600+4-1,600)=C(600+4-1,3)=36361101
                  ans
                  =S (全部)
                  -( (A>150 ) +(B>150 )+(C>150 )+(D>300 ))
                  +( (A>150 且B>150) +(A>150 且c>150) +(A>150 且D>150) ... )) 一共C(4,2)项没写完
                  - ((A>150 且B>150且C>150)+(A>150 且B>150且D>300))
                  + ((A>150 且B>150且C>150且D>300)
                  == 我写代码给你实现


                  IP属地:四川10楼2024-02-28 15:18
                  回复


                    IP属地:四川11楼2024-02-28 15:54
                    收起回复