PA06ANT - Ant

A Byteotian ant is walking along the edges of ABCDEFGH cube:

It tries to find out, in how many ways it can go from one given vertex, to another given vertex, walking along exactly k edges (when the ant enters an edge, it will not turn back and will finally reach the second end of this edge). If the ant goes through some edge x times, we count this edge x times. The ant would like to have interesting routes, that is if the ant is in some vertex, it would like to leave this vertex using an edge other than the edge recently used to enter this vertex (i.e. it want not to use the same edge twice in a row).

Our ant is not so smart, because it can only count using integers from 0 to p-1, for some p, so you should compute the result modulo p.


Write a program which:
* reads the starting and the ending vertex of the ant's route, number of edges on the ant's route, and integer p,
* computes number of interesting routes, which satisfy the ant's requests, modulo p,
* writes the answer to the standard output.


The first line of the standard input contains two capital English letters v1 and v2, separated by a single space. The two letters denote the starting and ending vertex of the ant's route respectively. The second line contains two integers k and p, separated by a single space.


Exactly one integer is to be written on the standard output. This integer is the number of interesting routes from the vertex v1 to the vertex v2, containing exactly k edges, modulo p.


3 100



* A ≤ v1, v2 ≤ H, v1 ≠ v2.
* 1 ≤ k ≤ 2 x 109, 2 ≤ p ≤ 109.

Được gửi lên bởi:AnhDQ
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:PA 2006 Round 5

hide comments
2021-05-27 18:02:50
Tham khảo:
2021-01-23 11:04:02
2018-06-15 18:05:00
code ac :
2015-08-30 04:10:34
bài thốn vãi :((
2015-05-04 01:01:05 Stupid Dog
đề gốc với hình :
2013-03-15 14:51:56 Chế Quốc Hữu
Cho em hỏi bài này trên đường đi có được phép qua điểm kết thúc không ạ?
2012-01-01 05:19:04 Noyethug
hjx.chán quá k xem đc cái hình..:(
2009-09-27 04:09:39 HaiZ
neu k=6 thi co' dc dj nhu the' nay` khong
A B C D A B ...

Last edit: 2009-09-27 04:10:42
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.