trang chủ / đề bài / icpc23_mb_i

Nim

Đề bài

Mô tả

Alice và Bob chơi một biến thể của trò chơi Nim.

Để chuẩn bị, đầu tiên Bob chọn một dãy tăng ngặt gồm N số nguyên A1,A2,A3,…,AN. Sau đó, Alice xếp K đống sỏi thành một hàng. Số sỏi trong mỗi đống phải là một số thuộc dãy của Bob. Các đống sỏi được phân biệt với nhau, nên có tổng cộng NK cấu hình ban đầu khác nhau.

Alice và Bob lần lượt thực hiện nước đi, Alice đi trước. Ở mỗi nước đi, người chơi phải chọn 1 hoặc 2 đống sỏi và bốc một số dương viên sỏi từ mỗi đống đã chọn. Được phép bốc số lượng khác nhau ở mỗi đống. Người không thể thực hiện nước đi hợp lệ sẽ thua.

Giả sử cả Alice và Bob đều chơi tối ưu, hãy đếm số cấu hình ban đầu mà Alice thua và Bob thắng. Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo 109+9.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên dương N và K: độ dài dãy của Bob và số đống sỏi (1≤N≤1000, 1≤K≤1018).
  • Dòng thứ hai chứa N số nguyên A1,A2,A3,…,AN: dãy số của Bob (1≤A1<A2<…<AN≤1000).

Dữ liệu ra

In ra đáp án, theo modulo 109+9.

Ràng buộc

  • 1≤N≤1000
  • 1≤K≤1018
  • 1≤A1<A2<…<AN≤1000

Ví dụ

Input Output Giải thích
2 3
1 2
2 Có 23=8 cấu hình. Alice thua ở đúng hai cấu hình (1,1,1) và (2,2,2).
9 123456789
1 2 3 4 5 6 7 8 9
552110917

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0