시간 제한메모리 제한제출정답맞은 사람정답 비율
5 초 (추가 시간 없음) 512 MB55201545.455%

문제

행렬식은 선형대수학에서 다루는 중요한 대상 중 하나이다.

  • 자연수 $n$에 대하여, $S_n$은 $\{1, 2, \cdots n\}$에서 $\{1, 2, \cdots n\}$으로 가는 모든 전단사함수의 집합이다. 
  • $\sigma \in S_n$에 대하여, $\text{inv}(\sigma)$는 $1 \le i < j \le n$과 $\sigma(i) > \sigma(j)$를 모두 만족하는 $(i, j)$의 개수이다.
  • 이때, $n \times n$ 행렬 $A$의 각 원소를 $a_{i, j}$라 하면, $A$의 행렬식은 $\text{det}(A) = \sum_{\sigma \in S_n} (-1)^{\text{inv} (\sigma) } \prod_{i=1}^n a_{i, \sigma(i)}$이다.

각 원소가 정수인 $N \times N$ 행렬 $A$가 있을 때, 다음 쿼리를 $Q$개 처리해보자.

  • 정수 $x$가 입력되면, $A - xI$의 행렬식의 값을 출력한다. 단, $I$는 $N \times N$ 단위행렬이다.

값이 지나치게 커질 수 있으므로, $998244353$으로 나눈 나머지를 출력하도록 한다.

입력

첫 줄에는 행렬의 크기 $N$과 쿼리의 개수 $Q$가 순서대로 주어진다. ($1 \le N \le 500$, $1 \le Q \le 250000$)

두 번째 줄부터 $N+1$번째 줄까지, 행렬 $A$의 원소들이 순서대로 입력된다. 즉, 

$a_{1,1}$ $a_{1,2}$ $\cdots$ $a_{1, n}$

$a_{2,1}$ $a_{2,2}$ $\cdots$ $a_{2,n}$

$\cdots$ $\cdots$ $\cdots$ $\cdots$

$a_{n,1}$ $a_{n,2}$ $\cdots$ $a_{n,n}$

과 같은 형식으로 행렬의 원소들이 주어진다. ($0 \le a_{i, j} < 998244353$)

$N+2$번째 줄에는 $Q$개의 쿼리가 차례대로 주어진다. 쿼리로 주어지는 모든 정수는 $0$ 이상 $998244353$ 미만이다.

출력

각 쿼리의 답을 순서대로 사이에 공백을 두고 한 줄에 출력한다.

예제 입력 1

3 6
2 4 5
6 3 8
1 6 3
10 9 5 8 3 1

예제 출력 1

407 470 402 495 260 110
W3sicHJvYmxlbV9pZCI6IjE5NTYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTWF0cml4IGFuZCBRdWVyaWVzIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1ODlcdWI4MmNcdWMyZGRcdWM3NDAgXHVjMTIwXHVkNjE1XHViMzAwXHVjMjE4XHVkNTU5XHVjNWQwXHVjMTFjIFx1YjJlNFx1YjhlOFx1YjI5NCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViMzAwXHVjMGMxIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzkwXHVjNWYwXHVjMjE4ICRuJFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMsICRTX24kXHVjNzQwJm5ic3A7JFxcezEsIDIsIFxcY2RvdHMgblxcfSRcdWM1ZDBcdWMxMWMgJFxcezEsIDIsIFxcY2RvdHMgblxcfSRcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MDRcdWIyZThcdWMwYWNcdWQ1NjhcdWMyMThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzc0XHViMmU0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT4kXFxzaWdtYSBcXGluIFNfbiRcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjLCAkXFx0ZXh0e2ludn0oXFxzaWdtYSkkXHViMjk0ICQxIFxcbGUgaSAmbHQ7IGogXFxsZSBuJFx1YWNmYyAkXFxzaWdtYShpKSAmZ3Q7IFxcc2lnbWEoaikkXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgJChpLCBqKSRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWI1NGMsICRuIFxcdGltZXMgbiQgXHVkNTg5XHViODJjICRBJFx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViOTdjICRhX3tpLCBqfSRcdWI3N2MgXHVkNTU4XHViYTc0LCAkQSRcdWM3NTggXHVkNTg5XHViODJjXHVjMmRkXHVjNzQwICRcXHRleHR7ZGV0fShBKSA9IFxcc3VtX3tcXHNpZ21hIFxcaW4gU19ufSAoLTEpXntcXHRleHR7aW52fSAoXFxzaWdtYSkgfSBcXHByb2Rfe2k9MX1ebiBhX3tpLCBcXHNpZ21hKGkpfSRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzAxIFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWM4MTVcdWMyMThcdWM3NzggJE4gXFx0aW1lcyBOJCBcdWQ1ODlcdWI4MmMgJEEkXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YjJlNFx1Yzc0YyBcdWNmZmNcdWI5YWNcdWI5N2MgJFEkXHVhYzFjIFx1Y2M5OFx1YjlhY1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM4MTVcdWMyMTggJHgkXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3NCwgJEEgLSB4SSRcdWM3NTggXHVkNTg5XHViODJjXHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgJEkkXHViMjk0ICROIFxcdGltZXMgTiQgXHViMmU4XHVjNzA0XHVkNTg5XHViODJjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMxMlx1Yzc3NCBcdWM5YzBcdWIwOThcdWNlNThcdWFjOGMgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsICQ5OTgyNDQzNTMkXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViM2M0XHViODVkIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDA2Y1x1YWUzMCAkTiRcdWFjZmMgXHVjZmZjXHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOCAkUSRcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxIFxcbGUgTiBcXGxlIDUwMCQsICQxIFxcbGUgUSBcXGxlIDI1MDAwMCQpPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICROKzEkXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCwgXHVkNTg5XHViODJjICRBJFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHVjOTg5LCZuYnNwOzxcL3A+XHJcblxyXG48cD4kYV97MSwxfSQmbmJzcDskYV97MSwyfSQmbmJzcDskXFxjZG90cyQmbmJzcDskYV97MSwgbn0kPFwvcD5cclxuXHJcbjxwPiRhX3syLDF9JCAkYV97MiwyfSQmbmJzcDskXFxjZG90cyQmbmJzcDskYV97MixufSQ8XC9wPlxyXG5cclxuPHA+JFxcY2RvdHMkJm5ic3A7JFxcY2RvdHMkJm5ic3A7JFxcY2RvdHMkICRcXGNkb3RzJDxcL3A+XHJcblxyXG48cD4kYV97biwxfSQgJGFfe24sMn0kICRcXGNkb3RzJCAkYV97bixufSQ8XC9wPlxyXG5cclxuPHA+XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVkNTg5XHViODJjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMCBcXGxlIGFfe2ksIGp9ICZsdDsgOTk4MjQ0MzUzJCk8XC9wPlxyXG5cclxuPHA+JE4rMiRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRRJFx1YWMxY1x1Yzc1OCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZmZjXHViOWFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHViMjk0ICQwJCBcdWM3NzRcdWMwYzEgJDk5ODI0NDM1MyQgXHViYmY4XHViOWNjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWNmZmNcdWI5YWNcdWM3NTggXHViMmY1XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjQ1MFx1YWNlMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxOTU2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRldGVybWluYW50IiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZGV0ZXJtaW5hbnQgaXMgb25lIG9mIHRoZSBpbXBvcnRhbnQgb2JqZWN0cyBjb3ZlcmVkIGluIGxpbmVhciBhbGdlYnJhLjxcL3A+XHJcblxyXG48cD5Gb3IgYSBuYXR1cmFsIG51bWJlciAkbiQsICRTX24kIGlzIHRoZSBzZXQgb2YgYWxsIHBlcm11dGF0aW9uczogZnVuY3Rpb25zIGZyb20gJFxcezEsIDIsIFxcbGRvdHMsIG5cXH0kIHRvICRcXHsxLCAyLCBcXGxkb3RzLCBuXFx9JCBzdWNoIHRoYXQgYWxsICRuJCB2YWx1ZXMgJGYoMSksIGYoMiksIFxcbGRvdHMsIGYobikkIGFyZSBkaWZmZXJlbnQuPFwvcD5cclxuXHJcbjxwPkZvciAkZiBcXGluIFNfbiQsICRcXG1hdGhpdHtpbnZ9KGYpJCBpcyB0aGUgbnVtYmVyIG9mIGludmVyc2lvbnMgaW4gcGVybXV0YXRpb24gJGYkOiB0aGUgbnVtYmVyIG9mIHBhaXJzICQoaSwgaikkIHN1Y2ggdGhhdCAkaSAmbHQ7IGokIGJ1dCAkZihpKSAmZ3Q7IGYoaikkLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciBtYXRyaXggJEEkIG9mIHNpemUgJE4gXFx0aW1lcyBOJC4gTGV0ICRhX3tpLGp9JCBiZSB0aGUgZWxlbWVudCBhdCByb3cgJGkkIGFuZCBjb2x1bW4gJGokLiBUaGUgPGVtPmRldGVybWluYW50PFwvZW0+Jm5ic3A7b2YgJEEkIGlzOjxcL3A+XHJcblxyXG48cD4kJCBcXGRldChBKSA9IFxcc3VtXFxsaW1pdHNfe2YgXFxpbiBTX259KC0xKV57XFxtYXRoaXR7aW52fShmKX0gXFxwcm9kXFxsaW1pdHNfe2k9MX1ee259IGFfe2ksZihpKX1cXHRleHR7Ln0gJCQ8XC9wPlxyXG5cclxuPHA+V2UgaGF2ZSBhbiAkTiBcXHRpbWVzIE4kIG1hdHJpeCAkQSQgd2hlcmUgZWFjaCBlbGVtZW50IGlzIGFuIGludGVnZXIuIExldCYjMzk7cyBydW4gJFEkIG9mIHRoZSBmb2xsb3dpbmcgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+V2hlbiB0aGUgaW50ZWdlciAkeCQgaXMgZ2l2ZW4sIHByaW50IHRoZSB2YWx1ZSBvZiB0aGUgZGV0ZXJtaW5hbnQgb2YgJEEgLSB4IEkkLCB3aGVyZSAkSSQgaXMgYW4gJE4gXFx0aW1lcyBOJCB1bml0IG1hdHJpeC48XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIHZhbHVlIGNhbiBiZSB0b28gbGFyZ2UsIHByaW50IHRoZSBhbnN3ZXIgbW9kdWxvIHByaW1lIG51bWJlciAkOTk4XFwsMjQ0XFwsMzUzJC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkTiQgYW5kICRRJCAoJDEgXFxsZSBOIFxcbGUgNTAwJCwgJDEgXFxsZSBRIFxcbGUgMjUwXFwsMDAwJCkuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0ICROJCBsaW5lcyBkZXNjcmliZSBtYXRyaXggJEEkLiBUaGUgJGkkLXRoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zICROJCBpbnRlZ2VycywgYW5kIHRoZSAkaiQtdGggb2YgdGhlc2UgaW50ZWdlcnMgcmVwcmVzZW50cyAkYV97aSxqfSQgKCQwIFxcbGUgYV97aSxqfSAmbHQ7IDk5OFxcLDI0NFxcLDM1MyQpLjxcL3A+XHJcblxyXG48cD5UaGVuICRRJCBsaW5lcyBmb2xsb3csIGVhY2ggY29udGFpbmluZyBvbmUgcXVlcnk6IGFuIGludGVnZXIgJHgkICgkMCBcXGxlIHggJmx0OyA5OThcXCwyNDRcXCwzNTMkKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSwgcHJpbnQgdGhlIGFuc3dlciBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Camp > Petrozavodsk Programming Camp > Summer 2020 > Day 6: Korean Contest K번

  • 문제를 만든 사람: rkm0959
  • 데이터를 추가한 사람: rkm0959