[UVa] 13298 - Fibonacci Family Formula

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13298 - Fibonacci Family Formula
Source            : UVA Online Judge
Category          : Linear Algebra
Algorithm         : Matrix Exponentiation
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll         long long int  
#define mod        1000000009  
  
static const int maxn = 100 + 2;  
  
struct Mat  
{  
      int row, column;  
      ll v[maxn][maxn];  
};  
  
inline Mat multiply(const Mat &A, const Mat &B)  
{  
      Mat ret;  
      ret.row = A.row;  
      ret.column = B.column;  
      for (int i = 0; i < A.row; i++)  
      {  
            for (int j = 0; j < B.column; j++)  
            {  
                  ll sum = 0;  
                  for (int k = 0; k < A.column; k++)  
                  {  
                        sum += (A.v[i][k] * B.v[k][j]) % mod;  
                        sum %= mod;  
                  }  
                  ret.v[i][j] = sum;  
            }  
      }  
      return ret;  
}  
  
inline Mat modPow(Mat mat, ll p)  
{  
      if (p == 1) return mat;  
      if (p & 1) return multiply(mat, modPow(mat, p-1));  
      Mat ret = modPow(mat, p >> 1);  
      return multiply(ret, ret);  
}  
  
ll arr[maxn];  
  
inline void Array(int k)  
{  
      arr[0] = 1;  
      for (int i = 1; i < maxn; i++)  
      {  
            int temp = k;  
            arr[i] = 0;  
            for (int j = i-1; j >= 0 && temp; j--)  
            {  
                  arr[i] = (arr[i] + arr[j]) % mod;  
                  --temp;  
            }  
      }  
}  
  
int main()  
{  
      // freopen("in.txt", "r", stdin);  
      int k;  
      ll n;  
      while (scanf("%d %lld", &k, &n) == 2)  
      {  
            if (k == 0 && n == 0) break;  
            Mat mat;  
            mat.row = k;  
            mat.column = k;  
            Array(k);  
            for (int i = 0; i < k; i++)  
            {  
                  for (int j = 0; j < k; j++)  
                  {  
                        mat.v[i][j] = 0;  
                        if (i == 0) mat.v[i][j] = 1;  
                        else if (i == j + 1) mat.v[i][j] = 1;  
                  }  
            }  
            if (n <= k)  
            {  
                  printf("%lld\n", arr[n]);  
            }  
            else  
            {  
                  mat = modPow(mat, n-k+1);  
                  ll sum = 0;  
                  for (int i = 0; i < k; i++)  
                  {  
                        sum += (mat.v[0][i] * arr[k-1-i]) % mod;  
                        sum %= mod;  
                  }  
                  printf("%lld\n", sum);  
            }  
      }  
}  

[UVa] 13277 - XOR Path

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13277 - XOR Path 
Source            : UVA Online Judge
Category          : Linear Algebra, Graph Theory
Algorithm         : Fast Walsh-Hadamard transform, dfs 
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll         long long  
6.   
7. static const int maxn = 1e5 + 5;  
8. static const int N    = 1<<16;  
9.   
10. template <typename T> struct FWT  
11. {  
12.       void fwt(T io[], int n)  
13.       {  
14.             for (int d = 1; d < n; d <<= 1)  
15.             {  
16.                   for (int i = 0, m = d<<1; i < n; i += m)  
17.                   {  
18.                         for (int j = 0; j < d; j++)  
19.                         {  
20.                               T x = io[i+j], y = io[i+j+d];  
21.                               io[i+j] = (x+y), io[i+j+d] = (x-y);  // xor  
22.                               //io[i+j] = x+y;                     // and  
23.                               //io[i+j+d] = x+y;                   // or  
24.                         }  
25.                   }  
26.             }  
27.       }  
28.       void ufwt(T io[], int n)  
29.       {  
30.             for (int d = 1; d < n; d <<= 1)  
31.             {  
32.                   for (int i = 0, m = d<<1; i < n; i += m)  
33.                   {  
34.                         for (int j = 0; j < d; j++)  
35.                         {  
36.                               T x = io[i+j], y = io[i+j+d];  
37.                               io[i+j] = (x+y)>>1, io[i+j+d] = (x-y)>>1; // xor  
38.                               //io[i+j] = x-y;                          // and  
39.                               //io[i+j+d] = y-x;                        // or  
40.                         }  
41.                   }  
42.             }  
43.       }  
44.       void convolution(T a[], T b[], int n)  
45.       {  
46.             fwt(a, n);  
47.             fwt(b, n);  
48.             for (int i = 0; i < n; i++) a[i] = a[i] * b[i];  
49.             ufwt(a, n);  
50.       }  
51.       void self_convolution(T a[], int n)  
52.       {  
53.             fwt(a, n);  
54.             for (int i = 0; i < n; i++) a[i] = a[i] * a[i];  
55.             ufwt(a, n);  
56.       }  
57. };  
58.   
59. struct node  
60. {  
61.     int v, w;  
62.     node() {}  
63.     node(int v, int w)  
64.     {  
65.         this->v = v;  
66.         this->w = w;  
67.     }  
68. };  
69.   
70. vector <node> graph[maxn];  
71. FWT <ll> fwt;  
72. ll arr[N+5];  
73.   
74. void dfs(int u = 1, int p = -1, int x = 0)  
75. {  
76.       arr[x]++;  
77.       for (auto &it : graph[u])  
78.       {  
79.             int v = it.v;  
80.             int w = it.w;  
81.             if (v == p) continue;  
82.             dfs(v, u, x^w);  
83.       }  
84. }  
85.   
86. int main()  
87. {  
88.       //freopen("in.txt", "r", stdin);  
89.   
90.       int tc;  
91.       scanf("%d", &tc);  
92.       for (int tcase = 1; tcase <= tc; tcase++)  
93.       {  
94.             int tnode;  
95.             scanf("%d", &tnode);  
96.             for (int e = 1; e < tnode; e++)  
97.             {  
98.                   int u, v, w;  
99.                   scanf("%d %d %d", &u, &v, &w);  
100.                   graph[u].push_back(node(v, w));  
101.                   graph[v].push_back(node(u, w));  
102.             }  
103.             dfs();  
104.             fwt.self_convolution(arr, N);  
105.             ll zero = (arr[0] - tnode) >> 1;  
106.             printf("Case %d:\n", tcase);  
107.             printf("%lld\n", zero);  
108.             for (int i = 1; i < (1<<16); i++) printf("%lld\n", arr[i]>>1);  
109.             for (int i = 0; i < maxn; i++) graph[i].clear();  
110.             fill(begin(arr), end(arr), 0);  
111.       }  
112. }