bzoj#P1009. [HNOI2008] GT 考试
[HNOI2008] GT 考试
题目描述
阿申准备报名参加 GT 考试,准考证号为 位数 ,他不希望准考证号上出现不吉利的数字。
他的不吉利数字 有 位,不出现是指 中没有恰好一段等于 。 和 可以为 。
输入格式
第一行输入 。
接下来一行输入 位的数。
输出格式
阿申想知道不出现不吉利数字的号码有多少种,输出对 取余的结果.
4 3 100
111
81
数据范围
对于 的数据,,,,。
阿申准备报名参加 GT 考试,准考证号为 n 位数 x1x2…xn,他不希望准考证号上出现不吉利的数字。
他的不吉利数字 a1a2…am 有 m 位,不出现是指 x1x2…xn 中没有恰好一段等于 a1a2…am。a1 和 x1 可以为 0。
第一行输入 n,m,K。
接下来一行输入 m 位的数。
阿申想知道不出现不吉利数字的号码有多少种,输出对 K 取余的结果.
4 3 100
111
81
对于 100% 的数据,0≤ai≤9,1≤n≤109,1≤m≤20,1≤K≤103。