c++ - 在SPOJ INCSEQ中获得WA-增加子序列

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。
                        
                        4年前关闭。
                                                                                            
                
        
我不知道为什么我要在第10种情况下获得WA，
我使用了BIT和Combination。
问题链接：SPOJ INCSEQ

问题详细信息：给定N（1≤N≤10,000）个整数S1，...，SN（0≤Si
这是My Code

我认为使用Mod函数的nCr存在问题。
   他们没有给出失败的测试用例，所以我没有任何失败的测试用例。

// Here i compute nCk
unsigned long long combination(ll n,ll k)
{
    unsigned long long ans=1;
    k=k>n-k?n-k:k;
    ll j=1;
    for(; j<=k; j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }
        else if(ans%j==0)
        {
            ans=ans/j*n;
        }
        else
        {
            ans=(ans*n)/j;
        }
    }
    return ans%mod;
}

请帮助

最佳答案

您的combination方法是错误的，因为对于较大的数字，nCr的结果将大于long long范围。

因此，有效利用模数可以避免这种情况下的溢出

我们知道还有另一种计算nCr的方法

我们知道

nCr = (n - 1)C(r - 1) + (n - 1)Cr

且由于k c：

int[][]c = new int[n + 1][k+1];
c[0][0] = 1;

for (int i = 1; i <= n; i++) {
    c[i][0] = 1;
    if(i <= k)
        c[i][i] = 1;
    for (int j = 1; j <= k; j++) {
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        c[i][j] %= mod;
    }
}

mod操作将确保我们的结果永远不会溢出。

关于c++ - 在SPOJ INCSEQ中获得WA-增加子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30321344/