Bellala's blog

By Bellala, history, 3 months ago, In English

615D - Multipliers

The way to solve this problem is easy. Just let $$$n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$$$ ($$$p_i$$$ are pairwise different) then the answer will be

$$$ ans=\prod_{i=1}^k \left(p_i^{1+2+\cdots +c_i}\right) ^ { (c_1+1)\cdots (c_{i-1}+1)(c_{i+1}+1)\cdots (c_k+1) } \mod p \\= \prod_{i=1}^k \left(p_i^{c_i(c_i+1)/2}\right) ^ { (c_1+1)(c_2+1)\cdots (c_{i-1}+1)(c_{i+1}+1)\cdots (c_k+1) \mod p-1} \mod p $$$

There're more than one way to get ans (a simple way is to use prefix product). But today I read a solution which I could not understand:

solution

My only question: why we can keep the factor 2 by mod 2*(mod-1)? Thanks in advance

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By Bellala, history, 5 months ago, In English

Some properties of bitwise operations seem very classical, but I had no idea of them until the first time I met them. Here are some examples: (^ is for bitwose XOR)

a+b = a&b + a|b

if a^b^c = 0, then (a-k)^(b-k)^(c-k)!=0 forall 0<k<=min(a,b,c)

a^b >= a-b (got it from uva12716 GCD XOR)

a+b = (a^b) + 2(a&b) (1451E1 - Битовые запросы (упрощенная версия))

There are countless blogs discussing the most basic properties like "a=b^c and b=a^c implies c=a^b", or tricks like "enumerate subsets with bitwise operations" and "swap two values without a third variable". But I didn't find what I need.

Can you give me a list of these special properties of bitwise operations? Or tell me that there's no need to know about them, everyone just derive them through the basic ones in a contest.

Read more »

 
 
 
 
  • Vote: I like it
  • +28
  • Vote: I do not like it

By Bellala, history, 5 months ago, In English

I was taught not to write things like a=a+++++a.

However I love writing a++ because I believe that it always gets executed after a whole sentence (perhaps, right after a , or ;?)

But today I wrote this and got WA:

if(hh < tt && a[hh+1] == a[hh]-1) c[hh+1] += 2*c[hh++];

wa code: 154812779

rewrote it like this and got AC:

if(hh < tt && a[hh+1] == a[hh]-1) c[hh+1] += 2*c[hh], hh++;

ac code: 154812722

I'm wondering if it's wrong somewhere else or am I misunderstanding the usage of x++?

Read more »

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

By Bellala, history, 6 months ago, In English

I've always believed that getting the inverse of some integer n this way takes O(log(p)) time:

long long inv(long long n, long long p) {
	if (n == 1) return 1;
	return inv(p%n, p) * (p - p/n) % p;
}

But recently someone told me that it might be O(sqrt(p)).

So what is the correct time complexity?

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By Bellala, history, 8 months ago, In English

I've been taught that if I don't write a 'return' for a non-void function, it will return a random value automatically. When I do so, my code runs well on 32-bit compilers (specifically, GNU G++ 14 & 17 on codeforces), but get TLE/RE on 64 bit compilers (64bit g++17 and 64bit g++20 on codeforces). Why?

Read more »

 
 
 
 
  • Vote: I like it
  • +28
  • Vote: I do not like it