int bigmod(int b, int p, int m){ int a; if (p == 0) return 1; if (p%2 == 0){ a = bigmod(b,p/2,m); return (a*a) % m; }else{ return ((b % m) * bigmod(b,p-1,m)) % m; } } int GCD(int a,int b) { while (b > 0) { a = a % b; a ^= b; b ^= a; a ^= b; } return a; } typedef struct{ int d; int x; int y; }ee; /*d = gcd(a,b) = ax + by*/ void extendedeuclid(int a, int b, ee *c){ ee data1; if (b == 0){ c->d = a; c->x = 1; c->y = 0; return; } extendedeuclid(b, a % b, &data1); c->d = data1.d; c->x = data1.y; c->y = data1.x - (a/b)*data1.y; return; } int LCS(){ int m,n; m = strlen(str); n = strlen(str2); for (i=1;i<=m;i++) c[i][0] = 0; for (j=0;j<=n;j++) c[0][j] = 0; for (i=1;i<=m;i++) for (j=1;j<=n;j++){ if (str[i-1]==str2[j-1]) c[i][j] = c[i-1][j-1] + 1; else if (c[i-1][j]>=c[i][j-1]) c[i][j] = c[i-1][j]; else c[i][j] = c[i][j-1]; } return c[m][n]; } unsigned int Divide_Conquer_Fib(int n) { unsigned int i,h,j,k,t,tmp; i = h = 1; j = k = 0; while (n > 0) { if (n%2 == 1){ t = j*h; j = i*h + j*k + t; i = i*k + t; } t = h*h; h = 2*k*h + t; k = k*k + t; n = n/2; } return j; } long long V[1005]; int coins[6] = {1,5,10,20,50,100}; for (i=0;i<=5;i++){ for (j=coins[i]; j<=1005; j++){ V[j] += V[j-coins[i]]; } } PRIMES SIEVE ------------------------------------------------------------- char p[MAX/2+5]; #define MAX 20000000 void sieve(){ unsigned int ii,jj,kk,tmp; p[0] = 0; tmp = sqrt(MAX+5); for (ii=0;ii<=tmp;ii++){ if (p[ii]==0){ for (jj=ii*3+3;jj b1[0].weight) return 1; return -1; } int istreedone(){ int ii; char c = intree[0]; for (ii=0;ii intree[e[ii].v2]){ cur = intree[e[ii].v1]; toconvert = e[ii].v2; }else{ cur = intree[e[ii].v2]; toconvert = e[ii].v1; } total += e[ii].weight; if (intree[toconvert] == 0){ intree[toconvert] = cur; }else{ toconvert = intree[toconvert]; for (jj=0;jj graph[ii][jj] && intree[jj] == 0) dis[jj] = graph[ii][jj]; } return total; } ------------------------------------------------------------- Bellman-Ford ------------------------------------------------------------- /*Bellman-Ford*/ dis[source] = 0; for (i=0;i tmp) dis[v] = tmp; } /*Detect negative cycle*/ flag = 0; for (i=0;i dis[u] + edges[i].weight){ flag = 1; break; } } ------------------------------------------------------------- Flody Warshall ------------------------------------------------------------- /*Initialisation*/ for (i=0;i w[i][k] + w[k][j]) w[i][j] = w[i][k] + w[k][j]; } ------------------------------------------------------------- Articulation points ------------------------------------------------------------- typedef struct{ int cnt; int vertex[105]; }adj; adj list[105]; int visit[105],d[105],low[105],pred[105],pts[105]; int min(int a, int b){ if (a < b) return a; return b; } void ArtPt(int u){ int ii,v,cnt=0; visit[u] = 1; low[u] = d[u] = ++time; for (ii=0;ii= d[u]){ pts[u] = 1; } }else if (v != pred[u]){ low[u] = min(low[u],d[v]); } } return; } ------------------------------------------------------------- Finding bridges ------------------------------------------------------------- void Bridgefinding(int u){ int ii,v; visit[u] = 1; low[u] = d[u] = ++time; for (ii=0;ii d[u]){ bridge[cnt].small = min(u,v); bridge[cnt].big = max(u,v); cnt++; } }else if (v != pred[u]){ low[u] = min(low[u],d[v]); } } return; } -------------------------------------------------------------- triangles in graph -------------------------------------------------------------- for x=1..n, adj[x] is the set: { y: y>x and (x,y) is in E }. flag[1..n] is a boolean array, with all elements initialized to 'false' count = 0 for x = 1 to n: for each y in adj[x]: flag[y] = true for each y in adj[x]: for each z in adj[y]: if flag[z] then: yield (x,y,z) count++ for each y in adj[x]: flag[y] = false -------------------------------------------------------------- NETWORK FLOW -------------------------------------------------------------- #define MAXINT 10000; int totalflow,sink,source; int pre[105], flow[105], visited[105], capacity[105][105]; int min(int a, int b){ if (a < b) return a; return b; } void networkflow(){ int maxflow, maxloc,curnode,nextnode; totalflow = 0; while (1){ for (i=1;i<=n;i++){ pre[i] = 0; visited[i] = 0; flow[i] = 0; } flow[source] = MAXINT; while (1){ maxflow = 0; maxloc = -1; for (i=1;i<=n;i++){ if (flow[i] > maxflow && visited[i]==0){ maxflow = flow[i]; maxloc = i; } } if (maxloc == -1) break; if (maxloc == sink) break; visited[maxloc] = 1; for (i=1;i<=n;i++){ if (capacity[maxloc][i]>0&&flow[i] < min(maxflow,capacity[maxloc][i])){ pre[i] = maxloc; flow[i] = min(maxflow,capacity[maxloc][i]); } } } if (maxloc == -1) break; totalflow += flow[sink]; curnode = sink; while (curnode != source){ nextnode = pre[curnode]; capacity[nextnode][curnode] -= flow[sink]; capacity[curnode][nextnode] += flow[sink]; curnode = nextnode; } } return; } ------------------------------------------------------------- DISJOINT SETS ------------------------------------------------------------- int parent[50100]; int rank[50100]; /*init set all parent[i] = i set all rank[i] = 0 */ void unionset(int a, int b){ a = findroot(a); b = findroot(b); if (a == b) return; if (rank[a] < rank[b]) parent[a] = b; else if (rank[a] > rank[b]) parent[b] = a; else{ parent[a] = b; rank[b]++; } return; } int findroot(int a){ int root,j; root = a; while (root != parent[root]) root = parent[root]; /*Path compression*/ j = parent[a]; while (j!=root){ parent[a] = root; a = j; j = parent[a]; } return root; } ------------------------------------------------------------- TRIE ------------------------------------------------------------- struct nodeT{ int end; struct nodeT *next[26]; }; struct nodeT root; struct nodeT nodes[10000]; void addWord(struct nodeT *p, char *word){ int ii, id,len = strlen(word); struct nodeT *v; for (ii=0;iinext[id]==NULL){ memset(&nodes[np],0x0,sizeof (struct nodeT)); p->next[id] = &nodes[np]; np++; } p = p->next[id]; if (ii == len - 1) p->end = 1; } return; } void printtrie(struct nodeT *p, int depth){ int ii,iszero; path[depth] = 0; if (p->end == 1){ printf("%s\n",path); } for (ii=0,iszero=1;ii<26;ii++){ if (p->next[ii] != 0){ path[depth] = ii+'a'; printtrie(p->next[ii],depth+1); iszero = 0; } } if (iszero != 0 && p->end == 0) printf("%s\n",path); return; } ... memset(&root,0x0,sizeof(struct nodeT)); ... AddWord(&root,word); ... printtrie(&root,0); ------------------------------------------------------------- QUEUES ------------------------------------------------------------- #define MAX 1000 int qhead, qtail, queue[MAX]; int isempty(){ if (qhead==qtail) return 1; return 0; } void enqueue(int a){ if ((qtail+1)%MAX == qhead){ printf("Overflow\n"); } queue[qtail++] = a; if (qtail >= MAX) qtail = 0; return; } int dequeue(){ int a; if (qhead == qtail) printf("Underflow\n"); a = queue[qhead++]; if (qhead >= MAX) qhead = 0; return a; } ----------------------------------------------------------------- #define MAX 1000 typedef struct{ int head; int tail; int q[MAX]; }queue; int isempty(queue *q1){ if (q1->head == q1->tail) return 1; return 0; } void enqueue(int a,queue *q1){ q1->q[q1->tail++] = a; if (q1->tail >= MAX) q1->tail -= MAX; return; } int dequeue(queue *q1){ int a; a = q1 -> q[q1->head++]; if (q1->head >= MAX) q1->head -= MAX; return a; } ------------------------------------------------------------------- Priority Queue ------------------------------------------------------------------- int nheap, Bheap[5500]; int min(int a, int b){ if (a < b) return a; return b; } void heapify(int a){ int T, k; if ((a*2) > nheap) return; T = min(Bheap[a],min(Bheap[a*2],Bheap[a*2+1])); if (T == Bheap[a]) return; if (T == Bheap[a*2]) k = a*2; else k = a*2+1; T = Bheap[a]; Bheap[a] = Bheap[k]; Bheap[k] = T; heapify(k); return; } void create(){ nheap = 0; return; } void insert(int a){ int T, tmp; nheap++; Bheap[nheap] = a; T = nheap; while (T != 1 && Bheap[T] < Bheap[T/2]){ tmp = Bheap[T]; Bheap[T] = Bheap[T/2]; Bheap[T/2] = tmp; T /= 2; } return; } int delete(int a){ int tmp; Bheap[a] = Bheap[nheap]; nheap--; heapify(a); while (a != 1 && Bheap[a] < Bheap[a/2]){ tmp = Bheap[a]; Bheap[a] = Bheap[a/2]; Bheap[a/2] = tmp; a /= 2; } return; }