FarmerAbdulAlim's blog

By FarmerAbdulAlim, 13 years ago, In English

Problem Link

I cannot optimize this code anymore. Please let me know how to optimize.

Thanks in advance. My Code

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

»
13 years ago, hide # |
← Rev. 4  
Vote: I like it +5 Vote: I do not like it
  • I have not solved it. But, if were in your situation I would try following ideas to get rid of TLE:-
  • Implement matrix mult(matrix &x,matrix &y) function in matrix bigmod(matrix b,LL p) function
  • r.mat[i][j]=sum%mod; can be replaced with while(r.mat[i][j]>=mod)r.mat[i][j]-=mod;
  • i would try to avoid long long data type and use some explicit cast when needed.
  • if that's also not enough i would try fastIO(use getchar() to take input).
  • Also read the comments after the problem statement. It might be helpful for you.
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it -8 Vote: I do not like it

In constant optimisation problems, especially in those which have enormous input data, it is good to write your own function for scanning integers. Below is the procedure i have used in many problems:

#define gc getchar_unlocked
inline int geti() {
  register int c = gc(), x = 0, sign = 1;
  for( ; c != '-' && (c < '0' || c > '9'); c = gc());
  if(c == '-') c = gc(), sign = -1;
  for( ; c >= '0' && c <= '9'; c = gc()) x = (x<<1) + (x<<3) + c-'0';
  return sign*x;
}
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The most significant thing you need to optimize is storing the result of base^2,base^4,base^8.... So when calculating base^n you can just multiply the corresponding power of twos like base^7 = base * base^2 * base^4

»
13 years ago, hide # |
← Rev. 2  
Vote: I like it +60 Vote: I do not like it

Nobody has really helped you, but your post got -8 rating. Codeforces community is so awful...

In fact, if you have an N × N matrix (let's call it M), it's possible to calculate ME × V (V is a vector) in , not in . To do so, you need to precalculate M1, M2, M4, M8.... Then, if you need to calculate, for example, M13 × V, you can just use the following formula: M13 × V = M8 × (M4 × (M1 × V)).

Sorry for my pidgin English, but in Russian (my native language) I'd explain this exactly the same way.

UPD. With this idea I instantly got AC in Java in 2.7s without any additional optimizations.

»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I got AC with a 3x3 matrix and optimizations, but I heard that there is a way of doing with just a 2x2 matrix. Can someone tell me how to find this 2x2 matrix?