小编CPP*_*der的帖子

我需要找到n!%1000000009.对于范围为1到20的k,n的类型为2 ^ k.我正在使用的函数是:

#define llu unsigned long long
#define MOD 1000000009

llu mulmod(llu a,llu b) // This function calculates (a*b)%MOD caring about overflows
{
    llu x=0,y=a%MOD;
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x = (x+y)%MOD;
        }
        y = (y*2)%MOD;
        b /= 2;
    }
    return (x%MOD);
}

llu fun(int n)   // This function returns answer to my query ie. n!%MOD
{
    llu ans=1;
    for(int j=1; j<=n; j++)
    {
        ans=mulmod(ans,j);
    }
    return ans;
}

我的要求是,我需要调用函数'fun',n/2次.对于15左右的k值,我的代码运行速度太慢了.有没有办法更快？

编辑:实际上我正在计算2*[(i-1)C(2 ^(k-1)-1)]*[((2 ^(k-1))!)^ 2]范围2 ^(k-1)到2 …

假设我已经声明了一个字符数组并从用户那里获取一个字符串,如下所示:

char s[100000];
std::cin>>s;

现在说用户输入了字符串"Program".我的角色数组如下:

'P''r''o''g''r''a''m''\0'......(99992 remaining indices with no/junk values)

有没有办法释放占用那些99992指数的空间？类似地,如果我有一个大小为100000的整数数组,并且我在运行时只使用前10个索引,那么有没有办法在我的程序运行期间调整我的数组大小.我知道我们可以为此目的使用向量但是有可能以某种方式使用数组吗？对于整数数组,我知道我们可以动态声明数组,然后按照我们的要求声明大小,但是说我有10个整数的数组,如下所示:

1 2 3 4 5 6 7 8 9 10

现在,我想只使用前9个索引和wnat来删除第10个索引.换句话说,随着动态分配,数组也可以动态删除吗？

编辑:我知道有可能使用STL,但我想知道我们是否可以在数组中做同样的事情？

我给了一个数字说N和它在数组中的相应位置.说给出的位置(指数)是:

4 5 8 11 13 15 21 28

我给了两个位置(指数)说x和y.设x = 7,y = 13.

我需要找到x和y之间有多少次出现的数字(包括y> = x).与上面的例子中一样,数字存在于位置x和y之间的位置8,11和13处,因此答案是3.

一个简单的方法是天真的O(n)算法,但我想利用这样的事实,即poistions总是按升序给出.我认为以修改的方式应用二进制搜索可能有所帮助,但我面临着麻烦.

// P is the array that stores positions(indices) of number
int start=0,End=n-1; // n is the size of array P
int mid=(start+End)/2;
int pos1=0,pos2=0;
while(End>start)
{
   mid=(start+End)/2;  
   if(P[mid]>=x && P[mid-1]<x && flag1!=0)
    {
        pos1=mid;
        flag1=0

    }
    if(P[mid]<=y && P[mid+1]>y && flag2!=0)
    {
        pos2=mid;
        flag2=0;
    }
    else if (P[mid]<x)
        start=mid;
    else
        End=mid;
 }
    int Number_Of_Occurence=(pos2-pos1);

你能否说一下我的代码可能出错的地方？