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

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 8 年前。

Improve this question

我不知道为什么我在第 10 个病例中得到了 WA，我使用了 BIT 和组合。问题链接:SPOJ INCSEQ

问题详细信息:给定一个由 N (1 ≤ N ≤ 10,000) 个整数组成的序列 S1, ..., SN (0 ≤ Si < 100,000)，计算 S 的长度为 K (1 ≤ K ≤ 50且K≤N)；即，满足 1 ≤ i1 < ... < iK ≤ N 且 Si1 < ... < SiK 的 K 元组 i1, ..., iK 的数量。

这里是My Code

我认为 nCr 使用 Mod 函数有问题。 他们不提供失败的测试用例，所以我没有任何失败的测试用例。

// 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;
}

请帮忙

Answer 1

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

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

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

我们知道

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

由于 k <= 50 很小，我们可以计算组合表 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;
    }
}

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