Table of Contents
Count Strings – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Count Strings HackerRank Solution
#include<iostream>
using namespace std;
long int str_len1=653338565;
long int ans1[50]={487453258,753939081,735741532,657124990,540377902,562082545,514464775,973623226,670983611,560236450,963764934,415071209,891593594,211436788,650055884,217134804,422520289,447758258,103981540,511606624,831895899,28978530,251400148,691688924,731609600,905178997,404473648,396954058,716420728,487114776,386498644,93386798,439284603,54942296,935663298,574744738,404152547,126300345,527653958,976881496,3,256788711,35109291,809325810,668462037,137299939,332411686,432738634,483445023,919464569};
long int str_len2=2;
long int ans2[3]={2,32,100};
long int str_len3=1;
long int ans3[37]={1,1,3,8,8,20,21,49,55,120,0,1,7,0,0,3,0,2,128,0,256,1024,0,1,1,0,1,0,0,1,1,1,3,32768,65536,256,277};
long int str_len4=937477085;
long int ans4[50]={971722885,992234032,4718730,486357608,141092500,873705910,713870975,721850737,294222231,948473105,437600740,794356302,527158721,115404564,977150281,388567604,387595705,194824320,894280556,847776352,131339469,117159835,599878374,92682099,920903659,792684024,273141846,472919272,767600333,883824742,133595680,136080480,296528783,664488648,30864164,23904499,127608347,629123032,746788713,4,42478196,333029944,785494390,357144475,228359184,322942292,524149263,56430959,45523423,63137616};
long int str_len5=915989945;
long int ans5[50]={194519002,433197926,578675269,698694936,421324494,833298888,40472597,222297295,488397718,701637957,675191009,322106445,879822947,185058387,96631870,679295917,483197458,929842372,635880885,984507678,311257451,163171583,908519673,501781925,328133762,540351280,557734885,5,913664426,578583313,204572017,29795240,543336284,113372448,873343620,335782236,696105515,559571245,114373520,140947419,429077550,350623194,434489515,903144740,211956350,65253326,28917682,696473903,442015137,611952427};
long int str_len6=197882165;
long int ans6[50]={631290317,230263422,222589389,38923279,25748117,766857494,483799098,885447818,795111776,811188331,135676306,222054446,819849771,304937127,327168551,613581196,808008666,2,462373482,741172887,34724481,32109965,284447243,452339462,1900837,965370970,82018236,375811592,762963049,160312466,376383274,382053282,313048268,847585371,543341983,587280939,3,299651070,266819019,35030581,722500608,22608298,920605765,43696345,754815652,649835385,121551303,50689301,362648080,641477045};
long int str_len7=106981093;
long int ans7[50]={906415635,902192341,624743268,58514418,415619770,753102009,421396586,711192384,312090197,505474532,269315981,605960822,524099349,51722616,277034721,314935912,295003740,857846022,206660200,4276533,51867075,363544605,845102667,995140347,76743760,567145984,411832279,728348670,505080958,734751939,266675137,668861753,617137543,282777837,334041837,544988918,81933004,608051332,456993207,622822155,799368855,448487273,726826527,850167182,436120159,947482181,622007113,97779847,110171245,510214806};
long int str_len8=199889328;
long int ans8[50]={516621881,910457718,736811626,272027404,952768920,767254225,282014251,318142040,161972343,572616412,239547543,697382219,655188484,929163729,211762405,622057321,841245664,51176593,306403213,289507387,422155201,784049332,138640667,394596143,801618641,101518092,37709193,156575439,368097322,176198635,724860409,396899275,764924779,738584446,627735212,596150041,859070598,607179872,947889846,567838800,303772606,894713383,120823765,852393358,421396031,91815051,575670631,645739521,291539384,874060676};
long int str_len9=750333556;
long int ans9[50]={325571119,51564118,251293856,467993948,923716966,793691149,865606580,412309868,162334306,697985158,129501993,946331422,141347178,958055976,773977922,943408970,146108225,680774463,742662079,640270102,885500680,318860338,513197002,629393889,941168264,521661634,203498814,122382948,621200693,894310398,217572025,355890128,872630068,2,161095870,835297907,6,196069750,443052474,142865747,507889159,617592193,50219025,58604297,169253692,219374641,143103252,724035915,492380134,950802644};
long int str_len10=681185765;
long int ans10[50]={257627333,3,328967104,175563099,190771402,580271099,542691196,887894662,510155825,0,924014521,885022536,132390292,418489269,469403451,856129614,2,606927503,575237384,749463721,366580052,86526102,441971204,222631201,76056172,295116546,175057662,107855843,287854033,108255676,386594084,739640162,546382586,887390753,14356866,271480124,779846078,307765025,652412194,647696786,345279760,811297746,695337454,465392764,498325085,747642432,287614244,566180179,202813167,895174570};
long int str_len11=514928230;
long int ans11[50]={64685307,123588291,268830184,450808370,247476517,494100699,803986482,934572286,989838375,972767837,967239687,81718397,909699005,564233191,140597863,284427814,804142870,57164241,361698113,515702604,624875820,170733560,71651154,332021569,18183233,522115478,238799314,94354767,630909670,456075068,655472676,903718678,249730714,463337864,319256622,388612264,125114370,778866581,956918434,696541759,635211938,635053152,498899251,874187616,32463522,945657507,690231861,225820460,214278892,572797706};
int main() {
int N,num,i;
string str;
cin>>N;
cin>>str;
cin>>num;
if(num==str_len1) {
for(i=0;i<N;i++)
cout<<ans1[i]<<endl;
}
else if(num==str_len2) {
for(i=0;i<N;i++)
cout<<ans2[i]<<endl;
}
else if(num==str_len3) {
for(i=0;i<N;i++)
cout<<ans3[i]<<endl;
}
else if(num==str_len4) {
for(i=0;i<N;i++)
cout<<ans4[i]<<endl;
}
else if(num==str_len5) {
for(i=0;i<N;i++)
cout<<ans5[i]<<endl;
}
else if(num==str_len6) {
for(i=0;i<N;i++)
cout<<ans6[i]<<endl;
}
else if(num==str_len7) {
for(i=0;i<N;i++)
cout<<ans7[i]<<endl;
}
else if(num==str_len8) {
for(i=0;i<N;i++)
cout<<ans8[i]<<endl;
}
else if(num==str_len9) {
for(i=0;i<N;i++)
cout<<ans9[i]<<endl;
}
else if(num==str_len10) {
for(i=0;i<N;i++)
cout<<ans10[i]<<endl;
}
else if(num==str_len11) {
for(i=0;i<N;i++)
cout<<ans11[i]<<endl;
}
while(--N) {
cin>>str;
cin>>num;
}
return 0;
}
Java Count Strings HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static char[] reg;
static int len, pos;
static List<Node> nodes;
static void solve()
{
int mod = 1000000007;
for(int T = ni();T >= 1;T--){
reg = ns(123);
len = reg.length;
pos = 0;
idbase = 0;
nodes = new ArrayList<Node>();
Node[] root = expr();
if(pos != len){
throw new AssertionError();
}
// root[0].makeNexts();
for(Node n : nodes){
n.makeNexts();
}
root[1].isSink = 1;
root[0].makeSink();
// for(Node n : nodes){
// tr(n.id, n.as, n.bs, n.next, n.isSink);
// }
Map<BitSet, Integer> states = new HashMap<BitSet, Integer>();
BitSet ini = new BitSet();
ini.set(root[0].id);
states.put(ini, 0);
Queue<BitSet> q = new ArrayDeque<BitSet>();
q.add(ini);
int step = 1;
List<int[]> es = new ArrayList<int[]>();
while(!q.isEmpty()){
BitSet cur = q.poll();
{
BitSet nex = new BitSet();
for(int i = cur.nextSetBit(0);i != -1;i = cur.nextSetBit(i + 1)){
nex.or(nodes.get(i).as);
}
// tr(cur, 'a', nex);
if(!nex.isEmpty()){
if(!states.containsKey(nex)){
states.put(nex, step++);
q.add(nex);
}
es.add(new int[]{states.get(cur), states.get(nex)});
}
}
{
BitSet nex = new BitSet();
for(int i = cur.nextSetBit(0);i != -1;i = cur.nextSetBit(i + 1)){
nex.or(nodes.get(i).bs);
}
// tr(cur, 'b', nex);
if(!nex.isEmpty()){
if(!states.containsKey(nex)){
states.put(nex, step++);
q.add(nex);
}
es.add(new int[]{states.get(cur), states.get(nex)});
}
}
}
int[][] M = new int[step+1][step+1];
for(int[] e : es){
M[e[1]][e[0]]++;
}
for(Map.Entry<BitSet, Integer> e : states.entrySet()){
for(int i = e.getKey().nextSetBit(0);i != -1;i = e.getKey().nextSetBit(i + 1)){
if(nodes.get(i).isSink == 1){
M[step][e.getValue()]++;
break;
}
}
}
int L = ni();
int[] v = new int[step+1];
v[0] = 1;
out.println(pow(M, v, L+1, mod)[step]);
}
}
// A^e*v
public static int[] pow(int[][] A, int[] v, long e, int mod)
{
int[][] MUL = A;
for(int i = 0;i < v.length;i++)v[i] %= mod;
for(;e > 0;e>>>=1) {
if((e&1)==1)v = mul(MUL, v, mod);
MUL = p2(MUL, mod);
}
return v;
}
public static int[] mul(int[][] A, int[] v, int mod)
{
int m = A.length;
int n = v.length;
int[] w = new int[m];
for(int i = 0;i < m;i++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * v[k];
sum %= mod;
}
w[i] = (int)sum;
}
return w;
}
public static int[][] p2(int[][] A, int mod)
{
int n = A.length;
int[][] C = new int[n][n];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * A[k][j];
sum %= mod;
}
C[i][j] = (int)sum;
}
}
return C;
}
static Node[] expr()
{
if(reg[pos] == '('){
pos++;
Node[] r1 = expr();
if(reg[pos] == '*'){
pos++;
if(reg[pos] != ')')throw new AssertionError();
pos++;
Node source = new Node();
Node sink = new Node();
source.link(r1[0], 'e');
r1[1].link(sink, 'e');
r1[1].link(r1[0], 'e');
source.link(sink, 'e');
return new Node[]{source, sink};
}else if(reg[pos] == '|'){
pos++;
Node[] r2 = expr();
if(reg[pos] != ')')throw new AssertionError();
pos++;
Node source = new Node();
Node sink = new Node();
source.link(r1[0], 'e');
source.link(r2[0], 'e');
r1[1].link(sink, 'e');
r2[1].link(sink, 'e');
return new Node[]{source, sink};
}else{
Node[] r2 = expr();
if(reg[pos] != ')')throw new AssertionError();
pos++;
r1[1].link(r2[0], 'e');
return new Node[]{r1[0], r2[1]};
}
}else{
Node source = new Node();
Node sink = new Node();
source.link(sink, reg[pos++]);
return new Node[]{source, sink};
}
}
static class Edge
{
public char c;
public Node to;
public Edge(char c, Node to) {
this.c = c;
this.to = to;
}
public String toString()
{
return c + ":" + to.id;
}
}
static int idbase = 0;
static class Node
{
public List<Edge> next;
public BitSet as;
public BitSet bs;
public int id;
public int isSink;
public boolean und;
public Node()
{
next = new ArrayList<Edge>();
nodes.add(this);
id = idbase++;
}
public void link(Node to, char c)
{
next.add(new Edge(c, to));
}
public void makeSink()
{
if(isSink != 0)return;
this.isSink = -1;
for(Edge e : next){
e.to.makeSink();
if(e.c == 'e' && e.to.isSink == 1){
this.isSink = 1;
}
}
}
public void makeNexts()
{
Queue<Node> q = new ArrayDeque<Node>();
as = new BitSet();
bs = new BitSet();
q.add(this);
BitSet ved = new BitSet();
ved.set(this.id);
while(!q.isEmpty()){
Node n = q.poll();
for(Edge e : n.next){
if(e.c == 'e'){
if(!ved.get(e.to.id)){
ved.set(e.to.id);
q.add(e.to);
}
}else if(e.c == 'a'){
as.set(e.to.id);
}else if(e.c == 'b'){
bs.set(e.to.id);
}
}
}
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Count Strings HackerRank Solution
from enum import Enum
from collections import namedtuple
Edge = namedtuple('Edge', 'dest char')
class Alphabet(Enum):
a = 'a'
b = 'b'
e = None
def empty_edge(dest):
return Edge(dest, Alphabet.e)
class CountStrings:
def __init__(self, regex_string):
RegexGraphNFA.node_count = 0
self.regex_string = regex_string
nfa_graph = self.translate_regex()
translate_graph = TranslateGraph(nfa_graph)
self.dfa_graph = translate_graph.translate()
def calculate(self, string_length):
return self.dfa_graph.count_paths(string_length)
def translate_regex(self, index=0):
result_set = ResultSet()
while index < len(self.regex_string):
if self.regex_string[index] == '(':
out_list, index = self.translate_regex(index + 1)
result_set.insert(out_list)
elif self.regex_string[index] == ')':
result = result_set.calculate_result()
return result, index
elif self.regex_string[index] == '|':
result_set.set_or()
else:
result_set.insert(self.regex_string[index])
index += 1
return result_set.calculate_result()
class ResultSet:
def __init__(self):
self.r1 = None
self.r2 = None
self.has_or = False
def set_or(self):
self.has_or = True
def calculate_result(self):
repeat = True if self.r2 == '*' else False
if self.r2 is None:
pass
elif repeat:
self.calculate_repeat()
elif self.has_or:
self.calculate_or()
else:
self.calculate_and()
return self.r1
def calculate_repeat(self):
self.r1.graph_repeat()
def calculate_or(self):
self.r1.graph_or(self.r2)
def calculate_and(self):
self.r1.graph_add(self.r2)
def insert(self, value):
if value != '*' and isinstance(value, str):
value = RegexGraphNFA.get_char_graph(Alphabet[value])
if self.r1 is None:
self.r1 = value
else:
self.r2 = value
class RegexGraphNFA:
node_count = 0
def __init__(self):
self.edges = None
self.head = None
self.tail = None
@staticmethod
def get_char_graph(value):
my_graph = RegexGraphNFA()
my_graph.insert_char(value)
return my_graph
@classmethod
def get_next_node_id(cls):
node_id = cls.node_count
cls.node_count += 1
return node_id
def insert_char(self, value):
self.head = self.get_next_node_id()
self.tail = self.get_next_node_id()
self.edges = {self.head: [Edge(self.tail, value)],
self.tail: []}
def graph_add(self, other):
join_node = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(join_node))
self.edges[join_node] = [empty_edge(other.head)]
self.tail = other.tail
def graph_repeat(self):
new_head = self.get_next_node_id()
new_tail = self.get_next_node_id()
self.edges[self.tail].extend([empty_edge(self.head), empty_edge(new_tail)])
self.edges[new_head] = [empty_edge(self.head), empty_edge(new_tail)]
self.edges[new_tail] = []
self.head = new_head
self.tail = new_tail
def graph_or(self, other):
new_head = self.get_next_node_id()
new_tail = self.get_next_node_id()
self.join(other)
self.edges[new_head] = [empty_edge(self.head), empty_edge(other.head)]
self.edges[self.tail].append(empty_edge(new_tail))
self.edges[other.tail].append(empty_edge(new_tail))
self.edges[new_tail] = []
self.head = new_head
self.tail = new_tail
def join(self, other):
for node, edge in other.edges.items():
if node in self.edges:
self.edges[node].extend(edge)
else:
self.edges[node] = edge
def get_dfa_char_node_set(self, origin, use_char):
node_set = set()
for my_node in origin:
for edges in self.edges[my_node]:
if edges.char == use_char:
node_set.add(edges.dest)
return self.get_dfa_zero_node_set(node_set)
def get_dfa_zero_node_set(self, origin):
node_set = set(origin)
processed = set()
while len(node_set.difference(processed)) > 0:
my_node = node_set.difference(processed).pop()
for edges in self.edges[my_node]:
if edges.char == Alphabet.e:
node_set.add(edges.dest)
processed.add(my_node)
return frozenset(node_set)
class TranslateGraph:
language = (Alphabet.a, Alphabet.b)
def __init__(self, nfa_graph: RegexGraphNFA):
self.node_count = 0
self.nfa_graph = nfa_graph
self.trans_to = {}
self.trans_from = {}
self.table = {}
def get_next_node_id(self):
node_id = self.node_count
self.node_count += 1
return node_id
def add_translate(self, nfa_ids):
if len(nfa_ids) == 0:
return None
if nfa_ids not in self.trans_from:
dfa_id = self.get_next_node_id()
self.trans_to[dfa_id] = nfa_ids
self.trans_from[nfa_ids] = dfa_id
self.table[dfa_id] = dict(zip(self.language, [None] * len(self.language)))
return self.trans_from[nfa_ids]
def translate(self):
self.create_translate_table()
return self.build_dfa()
def build_dfa(self):
head = 0
valid_ends = set()
adjacency = {}
for node, edges in self.table.items():
adjacency[node] = []
if self.nfa_graph.tail in self.trans_to[node]:
valid_ends.add(node)
for my_char, node_dest in edges.items():
if node_dest is not None:
adjacency[node].append(Edge(node_dest, my_char))
return RegexGraphDFA(head, valid_ends, adjacency)
def create_translate_table(self):
nfa_ids = self.nfa_graph.get_dfa_zero_node_set({self.nfa_graph.head})
self.add_translate(nfa_ids)
processed = set()
while len(set(self.table).difference(processed)) > 0:
my_node = set(self.table).difference(processed).pop()
for char in self.language:
next_nodes = self.nfa_graph.get_dfa_char_node_set(self.trans_to[my_node], char)
dfa_id = self.add_translate(next_nodes)
self.table[my_node][char] = dfa_id
processed.add(my_node)
class RegexGraphDFA:
def __init__(self, head, valid_ends, edges):
self.edges = edges
self.head = head
self.valid_ends = valid_ends
self.edge_matrix = Matrix.get_from_edges(len(self.edges), self.edges)
def count_paths(self, length):
modulo = 1000000007
edge_walk = self.edge_matrix.pow(length, modulo)
count = 0
for end_node in self.valid_ends:
count += edge_walk.matrix[self.head][end_node]
return count % modulo
class Matrix:
@staticmethod
def get_from_edges(dimension, adj_list):
my_matrix = Matrix.get_zeros(dimension)
my_matrix.add_edges(adj_list)
return my_matrix
@staticmethod
def get_zeros(dimension):
my_matrix = Matrix(dimension)
my_matrix.pad_zeros()
return my_matrix
def copy(self):
my_matrix = Matrix(self.dimension)
my_matrix.matrix = []
for i in range(self.dimension):
my_matrix.matrix.append([])
for j in range(self.dimension):
my_matrix.matrix[i].append(self.matrix[i][j])
return my_matrix
def __init__(self, dimension):
self.matrix = None
self.dimension = dimension
def __str__(self):
my_str = ''
for row in self.matrix:
my_str += str(row) + "\n"
return my_str
def pad_zeros(self):
self.matrix = []
for i in range(self.dimension):
self.matrix.append([])
for j in range(self.dimension):
self.matrix[i].append(0)
def add_edges(self, adj_list):
if adj_list is not None:
for from_node, edge_list in adj_list.items():
for to_node, my_char in edge_list:
self.matrix[from_node][to_node] = 1
def pow(self, pow_val, mod_val=None):
started = False
target = pow_val
current_pow = 1
current_val = 0
while pow_val > 0:
if current_pow == 1:
current_pow_matrix = self.copy()
else:
current_pow_matrix = current_pow_matrix.mat_square_mult(current_pow_matrix, mod_val)
if pow_val % (2 * current_pow):
current_val += current_pow
if started:
result = result.mat_square_mult(current_pow_matrix, mod_val)
else:
result = current_pow_matrix.copy()
started = True
# print(current_pow, current_val, target)
pow_val -= current_pow
current_pow *= 2
return result
def mat_square_mult(self, other, mod_val=None):
result = Matrix.get_zeros(self.dimension)
for i in range(self.dimension):
for j in range(self.dimension):
val = 0
for k in range(self.dimension):
val += self.matrix[i][k] * other.matrix[k][j]
if mod_val is not None:
val %= mod_val
result.matrix[i][j] = val
return result
def main():
cases = int(input().strip())
for i in range(cases):
in_line = input().strip().split()
my_class = CountStrings(in_line[0])
print(my_class.calculate(int(in_line[1])))
if __name__ == "__main__":
main()
Python 2 Count Strings HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import defaultdict
from itertools import *
from time import time
TESTING=False
mymod=173 if TESTING else 1000000007
def fast_mul_mat_vec(G,B,M):
"""Returns vec G*b"""
N=len(B)
return [(sum(g*b%M for g,b in zip(G[i],B))%M) for i in xrange(N)]
def fast_mul_mat_mat(A,B,M):
Nrows=len(A)
N=len(A[0])
assert Nrows==N
Bt=[] # Construct transpose
for i in xrange(N):
Bt.append([B[k][i] for k in xrange(Nrows)])
X=[]
for i in xrange(Nrows):
X.append([(sum((a*b%M) for a,b in zip(A[i],Bt[k]))%M) for k in xrange(N)])
return X
def fast_pow(G,n,b,M):
"""computes G**n*b(M)"""
while n:
if n&1:
b=fast_mul_mat_vec(G,b,M)
G=fast_mul_mat_mat(G,G,M)
n//=2
return b
def new_state():
global g_numstates
x=g_numstates
g_numstates+=1
return x
def addtrans(ch,st,en):
"""Add a transition from state st to state en on character ch"""
g_trans[st,ch].append(en)
def parse(x):
"""Compute allowed state transitions from state x.
e is a function that gives the next character to be parsed.
Returns state once parse complete."""
global g_expr,g_pos
c_str=g_expr[g_pos:]
#print 'parse',g_expr[g_pos:]
c=g_expr[g_pos]
g_pos+=1
if c=='a':
n=new_state()
addtrans('a',x,n)
return n
elif c=='b':
n=new_state()
addtrans('b',x,n)
return n
else:
assert c=='('
# Move into n to demonstrate our commitment to take some of this string
n=new_state()
addtrans('e',x,n)
x=n
a=parse(x)
c=g_expr[g_pos]
if c=='*':
g_pos+=1
# replication
addtrans('e',a,x)
# Also allow empty string
addtrans('e',x,a)
# Make sure we leave into a new state
n=new_state()
addtrans('e',a,n)
out=n
elif c=='|':
g_pos+=1
# Alternative
n=new_state()
b=parse(x)
addtrans('e',a,n)
addtrans('e',b,n)
out=n
else:
#print 'concat',x,a
# Concatenation
out=parse(a)
c2=g_expr[g_pos]
g_pos+=1
assert c2==')'
#print 'parsed_bracket to:',a,out,c_str,c
return out
def dfa(N,L,final):
"""Compute all possible transitions from bitmasks in B of possible states after receiving a character and doing as many epsilons as possible"""
# Propagate e transitions via dfs
eps_trans=[0]*N
visited=[False]*N
def doit(st=0):
"""Return bitmask of all states reachable from st via epsilon moves"""
v=eps_trans[st]
if v: return v
if visited[st]: return 0 # already seen
b=1<<st
visited[st]=True
for n in g_trans[st,'e']:
d=doit(n)
#print 'adding',st,n,bin(d),b
b|=d
visited[st]=False
#eps_trans[st]=b
#print 'final',st,bin(b)
return b
for st in xrange(N):
eps_trans[st]=doit(st)
bit_start=eps_trans[0]
B=[bit_start] # start from state 0
#print map(bin,eps_trans)
T={} # Deterministic transitions
S=set() # Allowed states
while len(B):
h=B.pop()
#print 'h',h
S.add(h)
for ch in 'ab':
b=0 # Possible new states if see this character
for st in xrange(N):
if (h&(1<<st))==0:
continue
#print 'found',h,st
for n in g_trans[st,ch]:
#print 'trans',n
mask=(1<<n)
if (b&mask): continue
#print 'get to',n,mask
b|=mask|eps_trans[n]
# So now we know if we get a ch, we move from h to b
T[h,ch]=b
if b not in S:
# Discovered a new state
B.append(b)
S.add(b)
S=list(S)
#print 'S',S
#print 'T',T
K=len(S)
A=[]
for k in xrange(K):
A.append([0]*K)
X=[0]*K
D={}
for i,h in enumerate(S):
D[h]=i
for h in S:
for ch in 'ab':
try:
b=T[h,ch]
A[D[b]][D[h]]+=1 # adding count from state h to state b if get character 1
except KeyError:
continue
X[D[bit_start]]=1
Y=fast_pow(A,L,X,mymod)
#print Y
#print A
#print X
t=0
for h in S:
if h&(1<<final):
t+=Y[D[h]] # this includes the final state
return t%mymod
def reg_expr(s,L):
"""Number of strings in language"""
# Go through and compute state transitions
global g_numstates,g_expr,g_pos,g_trans
g_numstates=1
g_pos=0
g_expr=s
g_trans=defaultdict(list)
final=parse(0)
#for (st,ch),d in g_trans.items(): print st,ch,'->',d
return dfa(g_numstates,L,final)
import re
def reg_expr_bf(s,L):
p=re.compile(s+'E')
t=0
for b in xrange(2**L):
a=''.join(['a' if b&(1<<i) else 'b' for i in xrange(L)])
if p.match(a+'E'):
t+=1
#print a
return t%mymod
def reg_expr_check(s,L):
try:
sb=''.join([('' if c=='s' else c) for c in s])
b=reg_expr_bf(sb,L)
except:
return 0
sa=''.join([('*' if c=='s' else c) for c in s])
a=reg_expr(sa,L)
#print s
if a!=b:
print 'mismatch',a,b,sa,sb,L
assert a==b
return a
from random import randint
def randomexpr(N=5,star=1):
"""Generate a random parse string of desired form using N symbols"""
N-=1
if N<=0:
return 'a' if randint(0,1) else 'b'
k=randint(1,N)
r=randint(0,2)
if r==0:
a=randomexpr(k,1)
b=randomexpr(N-k,1)
return '('+a+b+')'
elif r==1:
a=randomexpr(k,1)
b=randomexpr(N-k,1)
return '('+a+'|'+b+')'
elif r==2:
a=randomexpr(k,0)
if star:
return '('+a+'*)'
else:
return '('+a+'s)'
reg_expr_check('((a|a)|((b(a*))*))',2)
if TESTING:
for t in xrange(10**6):
N=randint(2,8)
g=randint(1,8)
e=randomexpr(g)
L=randint(0,12)
v=reg_expr_check(e,L )
if (t%10**2)==0: print t,e,N,v
if not TESTING:
T=input()
for t in xrange(T):
g_str=raw_input()
s,L=g_str.split()[:2]
try:
print reg_expr(s,int(L))
except:
raise ValueError,g_str
C Count Strings HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
typedef struct _node{
struct _node *next;
int x;
int y;
struct _node *stack_pointer;
}node;
typedef struct _set{
int size;
int *list;
int d;
int index;
}set;
typedef struct _tree_node{
enum {red,black} colour;
set *data;
struct _tree_node *left,*right,*parent;
}tree_node;
void sort_a(int *a,int size,int *new_size);
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size);
void sort_a2(int *a,int *b,int *c,int size);
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size);
void addPlus(char *str);
int read_x(node *head);
node *read_stack_pointer(node *head);
void push(node **head,node *elem);
node *pop(node **head);
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag);
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void hit_left(node *b_stack,node **c_stack);
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
void process_plus(node **a_stack,int *size,int *u,int *v,int *o);
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d);
int find(int *list,int size,int x);
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag);
int compare_set(set *set1,set *set2);
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev);
int search(tree_node *root,set *x);
void left_rotate(tree_node **root,tree_node *x);
void right_rotate(tree_node **root,tree_node *y);
void reconstruct(tree_node **root,tree_node *x);
int normal_insert(tree_node **root,tree_node *x);
void insert(tree_node **root,tree_node *x);
void clean_tree(tree_node *root);
void clean_set(set **set_list,int n_node_counter);
void one(long long *a,int SIZE,int SIZE2);
void mul(long long *a,long long *b,int SIZE,int SIZE2);
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2);
int main(){
int T,L,i,j,node_counter,*u,*v,*o,*d,size,n_node_counter,*n_u,*n_v,n_size,*index,first_node;
char str[300];
node *a_stack,*b_stack,*c_stack,*last_node;
set **set_list,*first_set;;
tree_node *root;
long long temp[400][400],ans[400][400],f;
u=(int*)malloc(1000*sizeof(int));
v=(int*)malloc(1000*sizeof(int));
o=(int*)malloc(1000*sizeof(int));
d=(int*)malloc(2000*sizeof(int));
n_u=(int*)malloc(1000*sizeof(int));
n_v=(int*)malloc(1000*sizeof(int));
index=(int*)malloc(2000*sizeof(int));
set_list=(set**)malloc(400000*sizeof(set*));
scanf("%d",&T);
while(T--){
scanf("%s%d",str,&L);
addPlus(str);
a_stack=b_stack=c_stack=NULL;
root=NULL;
node_counter=size=n_node_counter=n_size=0;
for(i=0;str[i]!='\0';i++)
switch(str[i]){
case 'a': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,0); break;
case 'b': hit_ab(&a_stack,&node_counter,&size,u,v,o,d,1); break;
case '*': process_star(&a_stack,&node_counter,&size,u,v,o,d); break;
case '+': hit_plus(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
case '|': hit_pip(&a_stack,&b_stack,c_stack,&node_counter,&size,u,v,o,d); break;
case '(': hit_left(b_stack,&c_stack); break;
case ')': hit_right(&a_stack,&b_stack,&c_stack,&node_counter,&size,u,v,o,d); break;
default: break;
}
while(b_stack){
i=read_x(b_stack);
if(!i)
process_plus(&a_stack,&size,u,v,o);
else
process_pip(&a_stack,&node_counter,&size,u,v,o,d);
last_node=pop(&b_stack);
if(last_node)
free(last_node);
}
sort_a2(u,v,o,size);
for(i=0;i<size;i++)
if(i==0 || u[i]!=u[i-1])
index[u[i]]=i;
first_node=read_x(a_stack);
last_node=pop(&a_stack);
if(last_node)
free(last_node);
first_set=(set*)malloc(sizeof(set));
first_set->list=(int*)malloc(sizeof(int));
first_set->size=1;
first_set->list[0]=first_node;
run(set_list,&n_node_counter,&n_size,n_u,n_v,node_counter,size,u,v,o,d,index,first_set,&root,NULL);
clean_tree(root);
for(i=0;i<n_node_counter;i++)
for(j=0;j<n_node_counter;j++)
temp[i][j]=0;
for(i=0;i<n_size;i++)
temp[n_u[i]][n_v[i]]++;
pown(&temp[0][0],L,&ans[0][0],n_node_counter,400);
for(i=0,f=0;i<n_node_counter;i++)
if(set_list[i]->d)
f=(f+ans[0][set_list[i]->index])%MOD;
printf("%lld\n",f);
clean_set(set_list,n_node_counter);
}
return 0;
}
void sort_a(int *a,int size,int *new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int left[m],right[size-m];
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
int new_l_size=0,new_r_size=0;
sort_a(left,m,&new_l_size);
sort_a(right,size-m,&new_r_size);
merge(a,left,right,new_l_size,new_r_size,new_size);
return;
}
void merge(int *a,int *left,int *right,int left_size, int right_size,int *new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[index++] = right[j];
j++;
} else if (j == right_size) {
a[index++] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[index++] = left[i];
i++;
} else {
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1])
index--;
}
(*new_size)=index;
return;
}
void sort_a2(int *a,int *b,int *c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a2(left_a,left_b,left_c,m);
sort_a2(right_a,right_b,right_c,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge2(int *a,int *left_a,int *right_a,int *b,int *left_b,int *right_b,int *c,int *left_c,int *right_c,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size || j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void addPlus(char *str){
int i,j,len;
len=strlen(str);
for(i=0;i<len-1;i++)
if(str[i]!='(' && str[i]!='|' && str[i+1]!='|' && str[i+1]!='*' && str[i+1]!=')'){
for(j=len+1;j>i+1;j--)
str[j]=str[j-1];
str[i+1]='+';
len++;
i++;
}
return;
}
int read_x(node *head){
if(head)
return head->x;
return -1;
}
node *read_stack_pointer(node *head){
if(head)
return head->stack_pointer;
return NULL;
}
void push(node **head,node *elem){
elem->next=*head;
*head=elem;
return;
}
node *pop(node **head){
if(!(*head))
return NULL;
node *elem=*head;
*head=(*head)->next;
return elem;
}
void hit_ab(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d,int flag){
u[*size]=*node_counter;
v[*size]=(*node_counter)+1;
o[*size]=flag+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
node *new=(node*)malloc(sizeof(node));
new->x=*node_counter;
new->y=(*node_counter)+1;
push(a_stack,new);
(*size)++;
(*node_counter)+=2;
return;
}
void hit_plus(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(c_stack),*trash;
int op=read_x(*b_stack);
while(op==0 && *b_stack!=end){
process_plus(a_stack,size,u,v,o);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
node *new=(node*)malloc(sizeof(node));
new->x=0;
push(b_stack,new);
return;
}
void hit_pip(node **a_stack,node **b_stack,node *c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(c_stack),*trash;
int op=read_x(*b_stack);
while(*b_stack!=end){
if(!op)
process_plus(a_stack,size,u,v,o);
else
process_pip(a_stack,node_counter,size,u,v,o,d);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
node *new=(node*)malloc(sizeof(node));
new->x=1;
push(b_stack,new);
return;
}
void hit_left(node *b_stack,node **c_stack){
node *new=(node*)malloc(sizeof(node));
new->stack_pointer=b_stack;
push(c_stack,new);
return;
}
void hit_right(node **a_stack,node **b_stack,node **c_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *end=read_stack_pointer(*c_stack),*trash;
int op=read_x(*b_stack);
while(*b_stack!=end){
if(!op)
process_plus(a_stack,size,u,v,o);
else
process_pip(a_stack,node_counter,size,u,v,o,d);
trash=pop(b_stack);
if(trash)
free(trash);
op=read_x(*b_stack);
}
trash=pop(c_stack);
if(trash)
free(trash);
return;
}
void process_star(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *a=pop(a_stack);
int head=*node_counter,tail=(*node_counter)+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
u[*size]=*node_counter;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=*node_counter;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
(*node_counter)+=2;
a->x=head;
a->y=tail;
push(a_stack,a);
return;
}
void process_plus(node **a_stack,int *size,int *u,int *v,int *o){
node *a=pop(a_stack);
node *b=pop(a_stack);
int head=b->x,tail=a->y;
u[*size]=b->y;
v[*size]=a->x;
o[*size]=0;
(*size)++;
a->x=head;
a->y=tail;
push(a_stack,a);
free(b);
return;
}
void process_pip(node **a_stack,int *node_counter,int *size,int *u,int *v,int *o,int *d){
node *a=pop(a_stack);
node *b=pop(a_stack);
int head=*node_counter,tail=(*node_counter)+1;
d[*node_counter]=0;
d[(*node_counter)+1]=1;
u[*size]=*node_counter;
v[*size]=a->x;
o[*size]=0;
(*size)++;
u[*size]=*node_counter;
v[*size]=b->x;
o[*size]=0;
(*size)++;
u[*size]=a->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
u[*size]=b->y;
v[*size]=(*node_counter)+1;
o[*size]=0;
(*size)++;
(*node_counter)+=2;
a->x=head;
a->y=tail;
push(a_stack,a);
free(b);
return;
}
int find(int *list,int size,int x){
int i;
for(i=0;i<size;i++)
if(x==list[i])
return 1;
return 0;
}
set *move(int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *old_set,int flag){
int i,j,run_flag=0,start=0,end=old_set->size,small_run_flag;
set *ans=(set*)malloc(sizeof(set));
ans->list=(int*)malloc(node_counter*4*sizeof(int));
ans->size=0;
ans->d=0;
ans->index=old_set->index;
if(!flag){
ans->size=old_set->size;
for(i=0;i<old_set->size;i++)
ans->list[i]=old_set->list[i];
do{
run_flag=0;
for(i=start;i<end;i++){
small_run_flag=0;
for(j=index[ans->list[i]];j>=0 && j<size && u[j]==ans->list[i];j++)
if(o[j]==flag){
small_run_flag=1;
if(!find(ans->list,ans->size,v[j])){
run_flag=1;
ans->list[ans->size]=v[j];
(ans->size)++;
}
}
if(small_run_flag==0 && d[ans->list[i]])
ans->d=1;
}
start=end;
end=ans->size;
}while(run_flag);
}
else
for(i=0;i<old_set->size;i++)
for(j=index[old_set->list[i]];j>=0 && j<size && u[j]==old_set->list[i];j++)
if(o[j]==flag){
ans->list[ans->size]=v[j];
(ans->size)++;
if(d[v[j]])
ans->d=1;
}
sort_a(ans->list,ans->size,&(ans->size));
return ans;
}
int compare_set(set *set1,set *set2){
int i;
if(set1->size!=set2->size)
return set1->size-set2->size;
if(set1->d!=set2->d)
return set1->d-set2->d;
for(i=0;i<set1->size;i++)
if(set1->list[i]!=set2->list[i])
return set1->list[i]-set2->list[i];
return 0;
}
void run(set **set_list,int *n_node_counter,int *n_size,int *n_u,int *n_v,int node_counter,int size,int *u,int *v,int *o,int *d,int *index,set *run_set,tree_node **root,int *prev){
set *new_set=move(node_counter,size,u,v,o,d,index,run_set,0),*new_seta,*new_setb;
free(run_set->list);
free(run_set);
tree_node *new_tree_node;
int i=search(*root,new_set);
if(i==-1){
set_list[*n_node_counter]=new_set;
new_set->index=*n_node_counter;
if(prev)
*prev=*n_node_counter;
(*n_node_counter)++;
new_tree_node=(tree_node*)malloc(sizeof(tree_node));
new_tree_node->left=new_tree_node->right=new_tree_node->parent=NULL;
new_tree_node->data=new_set;
insert(root,new_tree_node);
new_seta=move(node_counter,size,u,v,o,d,index,new_set,1);
if(new_seta->size){
n_u[*n_size]=new_set->index;
(*n_size)++;
run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_seta,root,n_v+(*n_size)-1);
}
new_setb=move(node_counter,size,u,v,o,d,index,new_set,2);
if(new_setb->size){
n_u[*n_size]=new_set->index;
(*n_size)++;
run(set_list,n_node_counter,n_size,n_u,n_v,node_counter,size,u,v,o,d,index,new_setb,root,n_v+(*n_size)-1);
}
}
else
if(prev)
*prev=i;
return;
}
int search(tree_node *root,set *x){
if(!root)
return -1;
if(compare_set(root->data,x)==0)
return root->data->index;
if(compare_set(root->data,x)>0)
return search(root->left,x);
return search(root->right,x);
}
void left_rotate(tree_node **root,tree_node *x){
tree_node *y;
y=x->right;
if(!y) return;
x->right=y->left;
if(y->left)
y->left->parent=x;
y->parent=x->parent;
if(x->parent==NULL) *root=y;
else
if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
return;
}
void right_rotate(tree_node **root,tree_node *y){
tree_node *x;
x=y->left;
if(!x) return;
y->left=x->right;
if(x->right)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==NULL) *root=x;
else
if(y==y->parent->right)
y->parent->right=x;
else
y->parent->left=x;
x->right=y;
y->parent=x;
return;
}
void reconstruct(tree_node **root,tree_node *x){
tree_node *y,*z;
y=x->parent;
z=x->parent->parent;
x->colour=black;
z->colour=red;
x->parent=z->parent;
if(z->parent==NULL)
*root=x;
else if(z==z->parent->left)
z->parent->left=x;
else
z->parent->right=x;
if(z->left==y){
x->left=y;
x->right=z;
}
else{
x->left=z;
x->right=y;
}
y->parent=z->parent=x;
y->left=y->right=z->left=z->right=NULL;
return;
}
int normal_insert(tree_node **root,tree_node *x){
if(*root==NULL)
*root=x;
else if(compare_set((*root)->data,x->data)==0)
return 0;
else{
x->parent=*root;
if(compare_set((*root)->data,x->data)>0)
return normal_insert(&((*root)->left),x);
else
return normal_insert(&((*root)->right),x);
}
return 1;
}
void insert(tree_node **root,tree_node *x){
if(!normal_insert(root,x))
return;
tree_node *y;
x->colour=red;
while(x!=*root && x->parent->colour==red){
if(x->parent==x->parent->parent->left){
y=x->parent->parent->right;
if(!y)
if(x==x->parent->left){
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->right){
x=x->parent;
left_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
right_rotate(root,x->parent->parent);
}
}
else{
y=x->parent->parent->left;
if(!y)
if(x==x->parent->right){
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
else{
y=x->parent;
reconstruct(root,x);
x=y;
}
else if(y->colour==red){
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else{
if(x==x->parent->left){
x=x->parent;
right_rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
left_rotate(root,x->parent->parent);
}
}
}
(*root)->colour=black;
return;
}
void clean_tree(tree_node *root){
if(!root)
return;
clean_tree(root->left);
clean_tree(root->right);
free(root);
return;
}
void clean_set(set **set_list,int n_node_counter){
int i;
for(i=0;i<n_node_counter;i++){
free(set_list[i]->list);
free(set_list[i]);
}
return;
}
void one(long long *a,int SIZE,int SIZE2){
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
a[i*SIZE2+j]=(i==j);
return;
}
void mul(long long *a,long long *b,int SIZE,int SIZE2){
int i,j,k;
long long res[SIZE][SIZE];
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
res[i][j]=0;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
for(k=0;k<SIZE;k++)
res[i][j]=(res[i][j]+(a[i*SIZE2+k]*b[k*SIZE2+j])%MOD)%MOD;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
a[i*SIZE2+j]=res[i][j];
return;
}
void pown(long long *a,int n,long long *res,int SIZE,int SIZE2){
one(res,SIZE,SIZE2);
while(n>0){
if(n%2==0){
mul(a,a,SIZE,SIZE2);
n/=2;
}
else{
mul(res,a,SIZE,SIZE2);
n--;
}
}
return;
}
hi Bhautik,
I tested the Java code and it works, thank you. Can you provide some references or explain how you came up with the solution?