문제 링크
- http://icpc.me/16122
풀이
0부터 시작해서 각 상태에 NOT 혹은 MINUS 연산을 적용시켰을 때 값이 어떻게 변하는지 트리로 그려보면, 이항 계수 꼴이 나온다는 것을 알 수 있습니다.
nCr를 998244353으로 나눈 나머지를 빠르게 구해주면 되는데, 998244353은 소수이므로 페르마의 소정리를 이용해서 빠르게 구해줄 수 있습니다.
전체 코드
1 |
|
0부터 시작해서 각 상태에 NOT 혹은 MINUS 연산을 적용시켰을 때 값이 어떻게 변하는지 트리로 그려보면, 이항 계수 꼴이 나온다는 것을 알 수 있습니다.
nCr를 998244353으로 나눈 나머지를 빠르게 구해주면 되는데, 998244353은 소수이므로 페르마의 소정리를 이용해서 빠르게 구해줄 수 있습니다.
1 |
|