Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: How Many Free Dimensions?
Description In calculating the outer product of vectors, existence of constraints usually makes it that not all the components of the product are independent of the others. For example, the outer product of two two-dimensional vectors a_{1}, a_{2}) and = (Bb_{1}, b_{2}), = C × A = (Bc_{11}, c_{12}, c_{21}, c_{22}). If we set c_{12} = c_{21}, then only three of the four components of is independent, or C has three free dimensions.CNow we have n components ^{k} = (Zz) where _{α}α enumerates all possible subscripts i_{1}i_{2}…i (1 ≤ _{k}i ≤ _{j}n for all j s.t. 1 ≤ j ≤ k). We can then apply a rule of constraint of the form s_{1}s_{2}…s=_{k}t_{1}t_{2}…t to the subscripts. Here _{k}s_{1}s_{2}…s and _{k}t_{1}t_{2}…t are two strings consisting of the same set of lowercase letters. A letter appearing in one string will also appear in the other one and it can have multiple occurrences in a string. When a rule is applied, the letters in it are replaced by arbitrary integers between 1 and _{k}n (inclusive) provided that the same letters are replaced by the same integers and different letters are replaced by different integers. If a resulted string after replacements is p_{1}p_{2}…p=_{k}q_{1}q_{2}…q, let _{k}α be p_{1}p_{2}…p and _{k}β be q_{1}q_{2}…q, then we set _{k}z = _{α}z. Given the number of vectors and their dimensions and a rule of constraint, you are required to compute the number of free dimensions of the product of the vectors._{β}Input The input contains several test cases. Each test case consists of two lines followed by a blank one. On the first line there are two integers which are Output For each test case, output one line containing the number of free dimensions of the product of vectors. Sample Input 2 2 ij=ji 3 3 iij=jii 0 0 Sample Output 3 21 Hint In the second test case in the sample input, the rule You can safely assume that all calculations can be done with 64-bit integers. Source POJ Monthly--2006.05.28, Liang, Shaochi |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator