In an iteration every ordered pair of manuals is merged into a new manual (a manual is merged with itself: old manuals are kept). So the number of manuals are squared in an iteration, but the number of manuals with a given requirement set (bit pattern) increases in a non-obvious way.
So instead of counting the number of manuals having exactly a given requirement set, try to count the manuals that have a subset of the given requirements (for all 2^N possible requirement selection):
So using modulo exponentiation an efficient solution is
// using that 2^(MOD-1) % MOD == 1
e = modexp(2, T, MOD-1)
// do transformations inplace
tosubset(Counts)
for i = 0 .. 2^N-1 {
// Counts[i] = Counts[i]^(2^T) % MOD
Counts[i] = modexp(Counts[i], e, MOD)
}
fromsubset(Counts)
// solution is Counts[2^N-1];
where Counts is the array that holds the initial manual
counts for every requirement set, MOD=1000000007 is prime and tosubset and
fromsubset are linear transfomations that change to and from
requirement subset counting.
A possible implementation of tosubset and fromsubset
// call it as tosubset(Counts, 0, 2^N)
void tosubset(int Counts[], int start, int len)
{
len = len / 2
if len == 0 {
return
}
tosubset(Counts, start, len) // transform first half: starts with 0 bit
tosubset(Counts, start+len, len) // transform second half: starts with 1 bit
for i = 0 .. len-1 {
// first half is a subset of second half
Counts[start+len+i] = (Counts[start+len+i] + Counts[start+i]) % MOD
}
}
void fromsubset(int Counts[], int start, int len)
{
len = len / 2
if len == 0 {
return
}
for i = 0 .. len-1 {
Counts[start+len+i] = (Counts[start+len+i] - Counts[start+i] + MOD) % MOD;
}
fromsubset(Counts, start, len)
fromsubset(Counts, start+len, len)
}