Editorials - C For Code 04 - Coding Club - ISM Dhanbad
Stan wants to know the Time
It was a cake walk problem. Here is its solution which is very easy to understand.
Cartman the Lazy Kid
Prerequisite: Warshall Floyd Algorithm
Here we need to find the all pair shortest paths. We make an
adjacency matrix for the graph and apply warshall Floyd Algorithm on it.
Here is the link for Warshall Floyd algorithm:
Butters Solves Recurrences
Prerequisite: Matrix Exponential
Method to solve recurrences
F(n) = 2*F(n-1) + 3*F(n-2)
Consider this matrix equation:
| F(n) |
= | 2
3 | * |
F(n-1) |
| F(n-1) | | 1
0 | |
F(n-2) |
Using this we can find nth term
in O(logn). To understand this method please read method 4 of this article
In problem 3:
ReplyDeleteF(n) = (3^n - (-1)^n) / 4
But the following code gives 'Wrong Answer':
---
#include
#define MOD 1000000007
using namespace std;
typedef long bigint;
bigint pow1(bigint n) {
if(n % 2) return -1;
return 1;
}
bigint pow3(bigint n) {
if(n == 0) return 1;
if(n == 1) return 3;
bigint p = pow3(n / 2);
p *= p;
p %= MOD;
if(n % 2) return (3 * p) % MOD;
return p;
}
bigint f(bigint n) {
return (pow3(n) - pow1(n)) / 4;
}
int main() {
int t;
bigint n;
cin >> t;
while(t--) {
cin >> n;
cout << f(n) % MOD << endl;
}
return 0;
}
Correction (on line 4):
Deletetypedef unsigned long long bigint;