A1293 | [COCI-2013_2014-contest2]#3 PALETA
来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Little Mirko spends his free time painting. For this hobby, he likes to use brushes and a pallet containing K colors overall. His friend Slavko decided to use Mirko's talent and gave him his new coloring book for Mirko to color. The coloring book contains N images numbered 1, 2, ..., N.
Mirko has decided to paint each image in exactly one color of the possible K colors from his pallet.
However, he really likes colorful things. He chose N numbers fi and decided to paint the image numbered i differently than the images numbered fi , except when fi = i. If fi = i, that means he can paint the image numbered fi whichever color he likes, as long as all other conditions have been met.
Mirko wants to know the number of possible ways to color Slavko's coloring book and he desperately needs your help! Calculate the number of possible ways to color the book. Given the fact that the output can be very large, print the answer modulo 1 000 000 00
7.
Mirko has decided to paint each image in exactly one color of the possible K colors from his pallet.
However, he really likes colorful things. He chose N numbers fi and decided to paint the image numbered i differently than the images numbered fi , except when fi = i. If fi = i, that means he can paint the image numbered fi whichever color he likes, as long as all other conditions have been met.
Mirko wants to know the number of possible ways to color Slavko's coloring book and he desperately needs your help! Calculate the number of possible ways to color the book. Given the fact that the output can be very large, print the answer modulo 1 000 000 00
7.
输入格式
The first line of input contains positive integers N, K (1 ≤ N, K ≤ 1 000 000).
Following line contains N numbers fi (1 ≤ fi ≤ N), the number stated in the text.
Following line contains N numbers fi (1 ≤ fi ≤ N), the number stated in the text.
输出格式
The first and only line must contain the number of possible ways to color Slavko's book.
输入输出样例
输入 #1
2 3 2 1
输出 #1
6
输入 #2
3 4 2 3 1
输出 #2
24
输入 #3
3 4 2 1 1
输出 #3
36
In test data worth 50% of total points, all numbers fi
will be different.
Clarification of the first example: Mirko has three colors and decided that the image numbered 2
mustn't be of the same color as the image numbered 1. The possible colorings are (1, 2), (1, 3), (2, 1),
(2, 3), (3, 1), (3, 2), where the first number in the brackets represents the color of the first image and the
second number the color of the second image.
Clarification of the fourth example: Mirko has four colors. There are no conditions regarding the
first image, it can be painted in whichever color. The second must be different than the first, and the
third different than the second. That means that those two images can be colored in the remaining 3
colors. This gives us a total of 36 combinations.
will be different.
Clarification of the first example: Mirko has three colors and decided that the image numbered 2
mustn't be of the same color as the image numbered 1. The possible colorings are (1, 2), (1, 3), (2, 1),
(2, 3), (3, 1), (3, 2), where the first number in the brackets represents the color of the first image and the
second number the color of the second image.
Clarification of the fourth example: Mirko has four colors. There are no conditions regarding the
first image, it can be painted in whichever color. The second must be different than the first, and the
third different than the second. That means that those two images can be colored in the remaining 3
colors. This gives us a total of 36 combinations.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted