Hi Codeforces, I'm wondering is it possible to calculate $$$C_n^k$$$ modulo $$$m$$$ with $$$n \leq 10^9, k \leq 10^5, m \leq 10^9$$$. I've already known that if $$$m$$$ is a big prime number (for example $$$10^9+7$$$), we can easily have an $$$O(k) \cdot log_2(m)$$$ algorithm using Fermat's little theorem to find the inverse modulo of number from $$$1$$$ to $$$k$$$. If $$$n$$$ is small (for example $$$n \leq 10^6$$$), we can use sieve to get rid of the dividing step, but if $$$n$$$ is big, I have no clue. Thanks in advance.

Hello Codeforces. I have just recently joined a contest at my school. In that contest, there was a problem requiring counting the number of shortest paths from a vertex s to every other vertex in a directed weighted graph. I have implemented my idea and tested it a bit so I had a strong belief that my code was correct. In the end, it turned out that the code was wrong. The contest gave me only one submission for each problem so I didn't have a chance to fix it during the contest. I have tried to find my mistakes in the code at home but I found nothing. Here is the code similar to what I submitted during the contest.

void Dijkstra (int s)
{
    // dist[i] is the minimum distance from s to i
    // num[i] is the number of shortest paths from s to i
    for (int i=1; i<=n; i++)
    {
        dist[i]=inf;
        num[i]=0;
    }
    dist[s]=0;
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    pq.push({0,s});
    num[s]=1;
    while (!pq.empty())
    {
        pair<int,int> tmp=pq.top();
        pq.pop();
        int u=tmp.second;
        for (auto g:adj[u])
        {
            // v is the adjacent vertex with u
            // w is the weight of the edge u-v
            int v=g.second;
            int w=g.first;
            if (dist[v]==dist[u]+w)
            {
                num[v]+=num[u];
            }
            if (dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                num[v]=num[u];
                pq.push({dist[v],v});
            }
        }
    }
}

Can anyone help me point out the mistake in the algorithm or maybe this was not the incorrect part in my initial code? I would be so grateful if you can provide a link to another problem that also requires counting the number of shortest paths so that I can test the code by myself. Thanks for reading and have a good day.

Hello peoples of codeforces, I just want to ask a question. Recently, I found debugging interactive problems' code manually kinda frustrating. Take this problem as an example. Having to answer the code's queries on my own is really time-consuming and one mistake means typing all over again. But if we could have another code that can simply read the original code's queries and answering them automatically then it would be really useful and convenient, especially when participating in a contest. If the problem was non-interactive, I would simply use files for input and output, but interactive problems require simultaneous interaction between two codes, which makes the solution of using files failed. So I am curious to know how to implement that. I would be so appreciative if someone can provide me a template in C++. Thanks for reading and have a nice day.

Hello peoples of codeforces, I hope you are doing well. This is my first blog and I want to ask a question: For people who can solve A, B, C Div 2 problems comfortably, how to improve their skills to solve harder problems within the contest time? I usually solve the first 3 problems from 45 minutes to 1 hour, but then I will find myself stuck coming up with a solution to the problem D. Without solving 4 or more problems per contest, I will never reach purple :(. Are there any tips for me to overcome that? Which tags do D problems usually have? What is the average rating of the 4th problems? I would appreciate your helping. Have a nice day.