[UVA][善用網路] 11028 - Sum of Product
|
Problem B |
Sum of Product |
|
Time limit: 1 second |
|
Given n, there can be n! circular arrangement of the numbers 0 to n-1.
Let’s represent every permutation as P1 P2 P3 … Pn!
SOP(Pk) = sum of product of every two contiguous numbers in Pk.
Consider an example where n = 4 and Pk = (1 3 2 0),
therefore SOP(Pk) = 1*3 + 3*2 + 2*0 + 0*1 = 9.
You have to find out the number of distinct values of SOP(Pk) for k = 1 to n!.
For n = 3,
|
Pk |
Permutation |
SOP(Pk) |
|
P1 |
0 1 2 |
2 |
|
P2 |
0 2 1 |
2 |
|
P3 |
1 0 2 |
2 |
|
P4 |
1 2 0 |
2 |
|
P5 |
2 0 1 |
2 |
|
P6 |
2 1 0 |
2 |
So, for n = 3, there is only 1 distinct value of SOP(Pk).
Input
There will be multiple test cases. Each case consists of a line containing a positive integer n (1 < n ≤ 20). The last line of input file contains a single 0 that doesn’t need to be processed. The total number of test cases will be at most 30.
Output
For each case, output the case number followed by the number of distinct SOPs.
|
Sample Input |
Output for Sample Input |
|
3 4 6 0 |
Case #1: 1 Case #2: 3 Case #3: 21 |
ProblemSetter: Sohel Hafiz
Next Generation Contest 2
自己硬暴幾筆之後，直接用網路資源搜尋一下相關序列。
http://oeis.org/search?q=1%2C3%2C8%2C21%2C43%2C69%2C102%2C145%2C197&language=english&go=Search
|
| For any circular arrangement of 0..n-1, let S = sum of squares of every sum of two contiguous numbers; then a(n) = # of distinct values of S. |
|
+20 3 |
|
| 1, 1, 1, 3, 8, 21, 43, 69, 102, 145, 197, 261, 336, 425, 527, 645, 778, 929, 1097, 1285, 1492, 1721, 1971, 2245, 2542, 2865, 3213, 3589, 3992, 4425, 4887, 5381, 5906, 6465, 7057, 7685, 8348, 9049, 9787, 10565, 11382, 12241, 13141, 14085, 15072, 16105 |
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
int n;
int res[] =
{1, 1, 1, 3, 8, 21, 43, 69, 102, 145,
197, 261, 336, 425, 527, 645, 778, 929, 1097, 1285,
1492, 1721, 1971, 2245, 2542, 2865, 3213, 3589};
int cases = 0;
while(scanf("%d", &n) == 1 && n) {
/*int a[30], i;
for(i = 0; i < n; i++)
a[i] = i;
set<int> S;
do {
int sum = 0;
for(i = 1; i < n; i++)
sum += a[i]*a[i-1];
sum += a[0]*a[n-1];
S.insert(sum);
} while(next_permutation(a, a+n));
printf("%d\n", S.size());*/
printf("Case #%d: %d\n", ++cases, res[n-1]);
}
return 0;
}
/*
1
1
1
3
8
21
43
69
102
145
197
*/