我有一个计数算法,我试图得到一个大致的描述.它是可怕的嵌套和可怕的指数.这里是:
1. For each T_i in T
2. For k = 1 to max_k
3. For each of 2^k*(n choose k) items
4. For each t in T_i
5. check if the item is in t...etc.
以下是每个运行时间的逐行概念
将所有这些相乘得出:
c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3
因为我想要一个大O表示,忽略常量给出:
k * 2^k * (n choose k) * (2^n)
众所周知,(n选择k)的上限为(n*e/k)^ k,因此:
O(k * 2^k …algorithm big-o combinatorics binomial-coefficients exponential
我想用以下约束计算 nCk mod m：
n<=10^18
k<=10^5
m=10^9+7
我读过这篇文章：
但是这里m的值为1009。因此使用卢卡斯定理，我们只需要计算aCb的1009*1009个不同值，其中a,b<=1009
如何在上述约束下做到这一点。我无法在给定的约束下制作 O(m*k) 空间复杂度的数组。
帮助！
c++ algorithm binomial-coefficients modulus modular-arithmetic
我想编写一个函数来使用尾递归找到C(n,k),我将非常感谢你的帮助.
我达到了这个:
(defun tail-recursive-binomial (n k)
(cond ((or (< n k) (< k 0)) NIL)
((or (= k 0) (= n k)) 1)
(T (* (tail-recursive-binomial (- n 1) (- k 1)) (/ n k)))))
使用二项式系数的以下属性.
但我不知道如何使递归调用成为每个实例执行的最后一条指令,因为最后一条指令是产品.我一直在尝试使用辅助功能,我认为这是唯一的方法,但我还没有找到解决方案.
我需要nCr mod p有效地计算.现在,我已经编写了这段代码,但它超出了时间限制.请建议更优化的解决方案.
对于我的情况, p = 10^9 + 7 and 1 ? n ? 100000000
我还必须确保没有溢出,因为nCr mod p保证适合32位整数,但n!可能超出限制.
def nCr(n,k):
r = min(n-k,k)
k = max(n-k,k)
res = 1
mod = 10**9 + 7
for i in range(k+1,n+1):
res = res * i
if res > mod:
res = res % mod
res = res % mod
for i in range(1,r+1):
res = res/i
return res
PS:我认为我的代码可能不完全正确.但是,它似乎适用于小的n正确.如果错了,请指出来!
我使用R代码：
dat<-data.frame(p1=c(0,1,1,0,0), GAMMA.1=c(1,2,3,4,3), VAR1=c(2,2,1,3,4), GAMMA.2=c(1,1,3,4,1))
form <- p1 ~ GAMMA.1:VAR1 + GAMMA.2:VAR1
mod <- glm(formula=form, data=dat, family=binomial)
(coef <- coefficients(mod))
# (Intercept) GAMMA.1:VAR1 VAR1:GAMMA.2
# 1.7974974 -0.2563667 -0.2181079
coef正如我们所看到的，交互的名称的GAMMA.2:VAR1顺序与form（我们VAR1:GAMMA.2改为）的顺序不同。由于多种原因，我需要输出
# (Intercept) GAMMA.1:VAR1 GAMMA.2:VAR1
# 1.7974974 -0.2563667 -0.2181079
之后无需更改系数的名称。具体来说，我希望系数的名称与我在form对象中使用的名称相同（无需像上面的代码中那样进行切换）。我可以告诉glm()不要切换交互的名称吗？
在C++中计算二项式系数的最佳方法是什么？我已经看到了一些代码片段,但在我看来,它总是只在某个特定区域可行.我需要一个非常非常可靠的计算.我尝试使用gamma功能:
unsigned n=N;
unsigned k=2;
number = tgammal(n + 1) / (tgammal(k + 1) * tgammal(n - k + 1));
但它在n = 8时已经不同,k = 2的1(并且n = 30,k = 2它崩溃).我"仅"需要计算大约至少n = 3000,其中k = 2.
当n和k为整数时，从n中选择k个对象的方式数，即二项式系数n!/(k!(nk)!)为整数。我怎样才能保证结果正确并且是整数类型？即使带有整数参数，该函数也会返回一个双精度值：choose
> typeof(choose(4L, 2L))
[1] "double"
与手动计算一样，例如n -choose-2 = n(n-1)/2
typeof((4L * (4L - 1L)) / 2L)
[1] "double"
当然，我可以强制转换为整数，as.integer()但我对机器精度感到紧张：
> as.integer(3.999999999999999)
[1] 3
> as.integer(3.9999999999999999)
[1] 4
round()（默认为digits=0）四舍五入到最接近的整数，但返回 double 类型的值。如果我可以确定提供以双精度格式存储的整数可以as.integer(round(...))保证四舍五入到正确的整数，而不会被机器精度绊倒，那么就是as.integer(round(choose(n, k)))可以接受的。是这样吗？或者是否有替代方法choose()可以为整数参数返回一个整数？
我需要n!/(n-r)!r!用C#来计算.对于小数字,使用阶乘函数很容易计算,但是当数字变得像100那样大时,它就不起作用了.有没有其他方法可以计算更大数字的组合？
我已经做了很多工作,但无法找到更大的测试用例的答案
在数学中,二项式系数是正整数族,在二项式定理中作为系数出现.C(n,k)表示从n个不同对象中选择k个对象的方式的数量.
然而,当n和k太大时,我们经常在模数运算后用素数P保存它们.请计算在P模数后n的二项式系数变为0的数量.
输入的第一个是整数T,即测试用例的数量.
以下T行中的每一行包含2个整数,n和素数P.
对于每个测试用例,输出一行包含\ tbinom nks的数量(0 <= k <= n),其中每个模数运算后的P为0.
3
2 2
3 2
4 3
1
0
1
我已经通过在二项式系数中使用余数定理完成了这个
#C(n,m) mod p
#n=l*p+t
#m=m*p+s
#then C(n,r) mod p=0 when (t<s or t=0)
inp1 = raw_input()
N=int(inp1)
result=[]
for i in range(N):
inp = raw_input()
a, b = [long(x) for x in inp.split(' ')]
j=0
#n=lp+t
t=a%b
t=t+1
l=a/b
j=l*(b-t)
result.append(j)
for i …我在最新版本的R中从glm计算OR置信区间时遇到问题,但我之前没有遇到过这个问题.任何glm在哪里family="binomial",无论模型多么简单,它都可以轻松地提取摘要和exp(coef(模型)),但是当我尝试提取confint()或者exp(confint(model)),"等待分析完成时... msgstr"显示消息并且没有任何反应(我等了10分钟然后取消了程序,这通常只需要几秒钟就能在我的机器上完成).什么可能绊倒这个功能的想法？我试过它multiple datasets和变量,结果相同.任何想法为什么需要这么长时间/未能完成？