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存在问题。
他们没有给出失败的测试用例,所以我没有任何失败的测试用例。
请帮助
且由于k c:
mod操作将确保我们的结果永远不会溢出。
想改善这个问题吗? 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/
10-10 16:53