| Submit | All submissions | Best solutions | Back to list |
ADACHES2 - Ada and Palaces |
Ada the Ladybug was playing chess against her good friend Velvet Mite Vinit. They came up with new figure, called palace. In fact, palace is just tower with king inside. It can attack as king and tower combined: Either anywhere to same column or row or anywhere to adjacent (by side or diagonal) field.
Their question is simple: How many ways can N palaces be placed on N×N chessboard so none of them attacks any other. Since this number might be pretty big, output answer modulo 109+7
Input
The first line of input will contain 1 ≤ T ≤ 105, the number of test-cases.
Each of the testcases will contain single integer 1 ≤ N ≤ 107, the size of chessboard.
Output
For each test-case output the number of possibilities modulo 1000000007.
Example Input
8 1 2 3 7 10 1000 10000 9999999
Example Output
1 0 0 646 479306 711794305 450342414 838796194
| Added by: | Morass |
| Date: | 2017-10-22 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
2018-10-22 14:58:27
How can one give this question under dp category when its formula based on series |
|
|
2018-07-30 17:33:10
I did spoj toolkit and then OEIS, and finally did not submit my code. How do you even expect people to come up with that sort of crazy formula on their own!? Last edit: 2018-07-30 17:33:49 |
|
|
2018-06-28 14:28:15
@va1ts7_100: Hi, well, as you pointed out.. don't gu futher than to "N" as parameter (yet indeed not a short way from here [well, in code it is, but.. :P ]) |
|
|
2018-03-30 20:01:40
I guess this problem involves dp with bit mask , but because of large value of n , I can't figure out how to create dp state . Can anyone give me some pointers to it @morass ? Last edit: 2018-03-30 20:06:35 |
|
|
2017-10-27 20:48:39
@Nitesh Bagmar: Good day to you... The judge data contains much more than 8 test-cases ..try to debug (for example take peek at first 36 test-cases ;-) ) |
|
|
2017-10-27 19:08:10 Nitesh Bagmar
@morass: can you please check submission# 20466914 once. It gives correct answer for each of the given cases and I don't see why it will give wrong answer unless the given input criteria is incorrect. |
|
|
2017-10-23 01:31:21
@Min_25: Thank you so much.. repaired! ^_^ |
|
|
2017-10-23 01:19:28 Min_25
In the sample case, T should be 8 instead of 9. Last edit: 2017-10-23 01:23:23 |
RSS