/ Vijos / 题库 /

夜夜的花裙子

夜夜的花裙子

背景

小岛哥哥:“做出来这一题,我送你花裙子好不好呀?”
少女夜夜:“好呀好呀!”

描述

图片

我们知道数字0~9可以用火柴棒表示出来。而减号可以用一根火柴棒表示出来,等于号可以用两根火柴棒表示出来。
现在给定N根火柴棒,有多少合法的"A-B=C"可以用恰好N根火柴棒摆出来呢?

这里,A,B,C都要求是正整数,且不允许有前导零,但是它们可以是一位数字,两位数字,三位数字,或者更多位数字。同时A,B,C的位数可以不一样。

格式

输入格式

输入有多组询问。第一行输入一个整数T,表示询问次数。
之后T行,每一行有两个整数N和M。

输出格式

对于每一组数据,以"Case #i: ans"的形式输出答案,其中答案为用N根火柴棒可以摆出来的合法"A-B=C"的个数,答案对M取余。

样例1

样例输入1

4
12 1000000007
17 1000000007
20 1000000007
147 1000000007

样例输出1

Case #1: 1
Case #2: 5
Case #3: 38
Case #4: 815630825

限制

对于20%的数据,1<=T<=10,5<=N<=24。
对于80%的数据,1<=T<=30,5<=N<=500。
对于100%的数据,1<=T<=1000,5<=N<=500,3<=M<=2000000000。

每一个测试点时限3秒。

信息

ID
1967
难度
7
分类
d 点击显示
标签
(无)
递交数
231
已通过
36
通过率
16%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

夜夜的模拟赛之十三岁的梦想