1267 . 保加利亞的對稱多項式

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

45.5% (10/22)

Tags

BULOI 2008-BULOI-fin

Description

一個關於 $N$ 個自變量 $x_1, x_2, …, x_N$ 的多項式被稱為一個「對稱多項式」若且唯若當這 $N$ 個變數做任意的交換時，這個多項式保持不變。舉個例子吧！當 $N=3$ 時，$x_1+x_2+x_3$ 以及 $x_1x_2+x_2x_3+x_3x_1$ 、$3x_1x_2+2x_2x_3+3x_1x_3+x_2x_3$ 這三個多項式都是對稱的，但是 $x_1x_2$ 這個多項式，雖然在 $N=2$ 時它是對稱，不過在 $N=3$ 的情形下它不對稱。請寫一個程式判斷給定的多項式是否對稱。

Input Format

輸入檔的第一列有一個正整數$K (0<K<21)$代表多項式的數量(也就是測試資料的筆數)。接下來會有$K$筆測試資料。
每一筆測試資料的第一列有兩個正整數$N,M(0<N<20,0<M<9999)$，分別代表自變量的個數以及該多項式的項數。
然後的$M$列，每列描述這個多項式的一項，它包含$N+1$個數字：第一個數字是該項的係數，然後的$N$個數字分別代表每一個自變量的冪。

所有係數都會在 $-99$ 到 $99$ 之間，並且任何一項中的任何一個自變量，其冪次皆小於$5$。

Output Format

請輸出一個長度為$K$的0-1字串，第$i$個字元若為$1$則代表了對應的第$i$個多項式為對稱多項式，為$0$則代表非對稱多項式。

Sample Input 1

2
3 1
1 1 1 0
3 4
3 1 1 0
2 0 1 1
3 1 0 1
1 0 1 1

Sample Output 1

01

Hints

Problem Source

原TIOJ1267 / Bulgarian National Olympiad in Informatics 2008 Final (Prob A6)

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 131072 262144 1
1 10000 131072 262144 2
2 10000 131072 262144 3
3 10000 131072 262144 4
4 10000 131072 262144 5
5 10000 131072 262144 6
6 10000 131072 262144 7
7 10000 131072 262144 8
8 10000 131072 262144 9
9 10000 131072 262144 10
10 10000 131072 262144 11
Submit
Back to Top