奇怪的查询codechef [英] Weird queries codechef

问题描述

我遇到了代码厨师的奇怪查询问题。

这是它的链接



我找到了一个很好的解决方案。但我无法理解。如果有人能解释这个会很好。这是代码..........

i came acrross weird queries problem on code chef .
Here is the link to it

I found a good solution for the same .But i could not understand it .It would be nice if anyone could explain this . Here is the code..........

#include <iostream>
#include<vector>
using namespace std;
//answer modulo
const int md = 1000000007;//(10^9+7)
const int MAX = 10010;
const int SOM = 100010;
const int N = 500010;//(5x10^5)
//1 ≤ Ai ≤ 10^5
int a[N];
int *p = &a[N];
//M array
vector<int> occ[N];
int PREC[MAX][MAX / 2];
int fact[SOM], invfact[SOM];
/*findings
occ, diff -vector array    
Constraints
1 ≤ M ≤ 5 × 10^5
1 ≤ Q ≤ 3 × 10^5
1 ≤ Ai ≤ 10^5
∑ 0 ≤ i < M Ai ≤ 3 × 10^6
For each query, 0 ≤ l ≤ r < M
1 ≤ k ≤ 10^5
0 ≤ n ≤ 10^5
*/
inline int add(int &a, int b)
{
    a += b;
    if (a >= md)
    {
        a -= md;
    }
}

inline int mul(int a, int b)
{   
    // prevetning overflow condition
    return (long long)a * b % md;
}

inline int pw(int a, int b)
{
    if (b == 1)
    {
        return a;
    }
    if (b == 2)
    {
        return (long long)a * a % md;
    }
    int res = 1;
    while (b > 0)
    {   //bitwise And
        if (b & 1)
        {
            res = mul(res, a);
            if (b == 1)
            {
                break;
            }
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

inline int inv(int x)
{
    return pw(x, md - 2);
}

inline int C(int n, int k)
{
    k = min(k, n - k);
    if (n <= 10000)
    {
        return PREC[n][k];
    }
    return mul(fact[n], mul(invfact[k], invfact[n - k]));
}


int main()
{
    printf("program started to function \n");
    //initializing first elt to be 1
    fact[0] = 1;    
    invfact[0] = 1;
 
    for (int i = 1; i < SOM; i++)
    {
        //mulitply two numbers
        fact[i] = mul(fact[i - 1], i);
        
        invfact[i] = inv(fact[i]);
    }
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX / 2; j++)
        {
            if (j == 0)
                PREC[i][j] = 1;
            else if (i == 0)
                PREC[i][j] = 0;
            else
            {
                PREC[i][j] = PREC[i - 1][j] + PREC[i - 1][j - 1];
                if (PREC[i][j] >= md)
                    PREC[i][j] -= md;
            }
        }
    }
    int m, tt;
    printf("\n Enter the array size and no of queries:");
    scanf("%d %d", &m, &tt);
    /*
    printf(" \n printing m and tt :%d %d", m , tt);
    */
    for (int i = 0; i < N; i++)
    {   
        
        occ[i].clear();
    }
    printf("\n Enter the array elements");
    for (int i = 0; i < m; i++)
    {
        scanf("%d", a + i);
       

        occ[a[i]].push_back(i);
        /*
        printf("\n value of a [i] is : %d", a[i]);
        printf(" The Element %d is stored at %u\n", a[i], (p + i));
        printf("\n");

        printf("\n value of occ [a[i]] is : %d",occ[a[i]]  );
        printf("\n value of occ[i] is : %d", occ[i]);
        printf("\n");
        */
       
    }
    vector<int> diff;
    for (int i = 0; i < N; i++)
    {
        if (!occ[i].empty())
        {
            //entering the i values into difference arrray
            diff.push_back(i);
            //printf("\n Diff array values diff[i] is :%d", diff[i]);
        }
    }
    // This loop executes till the tt variable is 0
    while (tt--)
    {
        //printf("\n while loop is executed");
        int l,r, n, k;
        printf("\n Enter query params");
        scanf("%d %d %d %d",&l,&r, &n, &k);
        printf("\n Printing query params:");
        printf("\n values of l r n k is: \t %d %d %d %d",l,r,n,k);
        
        if (n == 0)
        {   printf("\n n value is 0");
            printf(" \n %d", 1);
            continue;
        }
        //checking if input is greater than 10^9
        // reducing overflow
        /*
        double multiply = (n - 1) * 1LL * (k - 1);
        printf("\n printing multiplication result : %d", multiply);         
        */
        if ((n - 1) * 1LL * (k - 1) > 1e9)
        {
            // executes upon overflow condition
            printf("%d\n", 0);
            continue;
        }
        int sub = (n - 1) * (k - 1);
        printf("\n Sub value : %d", sub);
        int ans = pw(fact[n], r - l);
        printf("\n Ans value after pw function:%d",ans);
        for (int i = 0; i < (int)diff.size(); i++)
        {
            int num = diff[i];
            int cnt = lower_bound(occ[num].begin(), occ[num].end(), r + 1) -
                      lower_bound(occ[num].begin(), occ[num].end(), l);
            if (cnt == 0)
            {
                continue;
            }
            int x = num - sub;
            int y = n;
            if (x < y)
            {
                ans = 0;
                break;
            }
            int z = C(x, y);
            ans = mul(ans, pw(z, cnt));
        }
        printf("\n Answer is : %d", ans);
    }
    return 0;
}

我的尝试：



i给出了一些我能理解的评论。

问题链接：比赛页面| CodeChef [ ^ ]

推荐答案

使用调试器查看代码执行情况，它可以帮助您了解它是如何解决问题的。



有一个允许您查看代码正在执行的工具，其名称为调试程序。它也是一个很好的学习工具，因为它向你展示了现实，你可以看到哪种期望与现实相符。

当你不明白你的代码在做什么或为什么它做它做的时候，答案就是答案是调试器。

使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量。



调试器 - 维基百科，免费的百科全书 [ ^ ]



掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]

使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]

调试器在这里向您展示您的代码正在做什么，您的任务是与什么进行比较应该这样做。

调试器中没有魔法，它没有找到错误，它只是帮助你。当代码没有达到预期的效果时，你就会接近一个错误。

Use the debugger to see the code perform, it may help you to understand how it solve the problem.

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

这篇关于奇怪的查询codechef的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！