About Me - Introduction

blogs will be available weekly, days are already hectic, mini tests coming up, classes are trash i dont like it ,i dont like college at all, its just attendance and boring lectures that i personally dont want to and cant understand. my hours are consumed by codeforces i really want to do something else maybe records shortfilms,make music on fl studio, i think i need a break.
i dont want to waste away everything on dsa/cp so i also registered for few hackathons. its kind of refreshing to get your mind off one thing to another to keep yourself busy.
Pull your Luck if you notice,(f)+(f-1)+...1 is just sum of first f elements so you had to first create a prefix vector to store sum of first ith elements in the ith index, what should be the size of the vector? take max space as k<=10^12. Now the problem is for each n you cant iterate the prefix vector until 10^5 thats too much, you have to strip it down. as we are dealing with a circular instrument so maybe we have periodicity in the (x+ pref[i])%n==0 ==> take for example T(f)= f*(f+1)/2, now take T(f+2n)= (f+2n)*(f+2n+1)/2.
T(f+2n)-T(f) =n(2f + 2n + 1).
which implies T(f+2n)==T(f)mod(n).
hence T(f) repeats after every 2n that means we dont need to check beyond 2n. and lower bound is p. only iterate from 0 to min(p, 2n)
Living Sequence this was good fundamental problem that i didnt see before: refer this removing k.

I read two chapters of Goodbye Eri, its beautiful, the panels speaks through.BEAUTIFUL. Tatski Fujimoto i rlly rlly love how you draw especially the light and empty panels, its like youre making a movie but on a paper, i love it love it!!!!

today i learned rlly beautiful shit :: Binomial coeff modulo m where m is prime. in cp most times m is 1e9+7 which is witty enuf prime. when you take out factorials nCr you have to keep in mind the constraints you cannot process alot of factorials, so we come up with many ways of figuring out. first we look over optimum ways of calculating nCr, refer this :: Program to calculate value of nCr
look at the expected approach O(r) time and O(1) space,


        for (int i = 1; i <= r; i++){
            sum = sum * (n - r + i) / i;
        }
        return (int)sum;

now we look over the binomial coeff mod m link, in that we see several ways of calculating shit,most optimum is to use inverse modulo :: when we do sum = sum*(n-r+i)/i. we simply convert this to sum*(n-r+i)*(i^-1)mod m
use famous fermats little theorem: a^(p-1)==1modp where gcd(a,p)=1.
tweak this a little bit to get: a^(p-2)==a^-1modp. so basically i^-1 modm is same as pow(i,m-2)modm this makes our job easier: now we get:


            long long ncr(long long n, long long r){
        if (r < 0 || r > n || n < 0) return 0;
        long long sum=1; 
        for(long long i=1;i<=r;i++){
            long long num = (n-r+i)%mod;
            sum=sum*num%mod; 
            sum= sum* power(i, mod-2)%mod; 
        }
        return sum;
    }

in this you have to modify the power function to give the power in modm form to not get overflow.

another great way is to precalculate the both factorial and inverse of factorial using for loop but at each iteration you make sure to take modm. to find out the inverse of factorial.
nCr= n!/(n-r)!(r!)
nCr modm can be written as in inverse modulo form: n!modm*((n-r)! ^-1)modm*(r!^-1)modm


            void build(ll MAXN){  // to precompute 
    inversion.assign(MAXN+1,1); 
    fact.assign(MAXN+1,1); 
    for(ll i=1;i<=MAXN;i++){
        fact[i]=fact[i-1]*i%mod; 
    }
    inversion[MAXN] = pow(fact[MAXN],mod- 2);
    for (int i=MAXN;i>=1;i--) inversion[i-1]=inversion[i]*i%mod; 
}
ll ncr(ll n,ll r){ // to evaluate the final result
    if (r < 0 || n < 0 || r > n) return 0;
    return fact[n]*(inversion[n-r])%mod * inversion[r]%mod; 
}

follow my everyday blogs, youre going to witness my life ramming and unfolding infront of your eyes!!