-
Notifications
You must be signed in to change notification settings - Fork 24
Expand file tree
/
Copy pathAdjacentSwaps.html
More file actions
13 lines (13 loc) · 4.08 KB
/
AdjacentSwaps.html
File metadata and controls
13 lines (13 loc) · 4.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>Cat Taro has N cards. He arranged the cards in a row and wrote numbers 0 through N-1 on them from left to right. He wants to rearrange them so that <b>p</b>[i] is written on the i-th (0-indexed) card from the left.
<br></br>
<br></br>
He asked N-1 rabbits to rearrange the cards. The rabbits are numbered from 0 to N-2, and the i-th rabbit can swap the i-th and the (i+1)-th card from the left. A permutation of rabbits q[0], ..., q[N-2] is called <i>good</i> if having the rabbits performed exactly their operations in this order, <b>p</b>[i] is written on the i-th card from the left.
<br></br>
<br></br>
Return the number of <i>good</i> permutations of rabbits, modulo 1,000,000,007.
</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>AdjacentSwaps</td></tr><tr><td>Method:</td><td>theCount</td></tr><tr><td>Parameters:</td><td>vector <int></td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int theCount(vector <int> p)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>p</b> will contain between 2 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>p</b> will be between 0 and N-1, inclusive, where N is the number of elements in <b>p</b>.</td></tr><tr><td align="center" valign="top">-</td><td><b>p</b> will contain no duplicate elements.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 2, 0}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1</pre></td></tr><tr><td><table><tr><td colspan="2">Initially {0, 1, 2} are written on the cards from left to right.
There are two permutations of rabbits:
<ul>
<li>Rabbit 0 -> rabbit 1. After rabbit 0 performs an operation, the cards become {1, 0, 2}. After rabbit 1 performs an operation, the cards become {1, 2, 0}.</li>
<li>Rabbit 1 -> rabbit 0. After rabbit 1 performs an operation, the cards become {0, 2, 1}. After rabbit 0 performs an operation, the cards become {2, 0, 1}.</li>
</ul></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{0, 1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2">The rabbit must perform an operation.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{2, 0, 3, 1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 0, 3, 2}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15, 19, 17}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 716743312</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>