A.趣味三角(triangle.cpp) 

【题目描述】 

今天，新高一的OIer们第一次进入了机房。z老师想让他们喜欢上OI，于是给了他们每个人一个三角形。 这时候，小q秃发奇想，拿着手中的三角形，给大家出了一道题，请你帮助他们给小q一个正确的答案。 小q给了你两个整数 ，请输出杨辉三角前x行的所有数的和模a的值。 如果你不知道杨辉三角是什么，请看样例解释。 

【输入格式】

 每个测试点有多组测试数据。 每个测试点第一行一个正整数n表示数据组数。 接下来n行每行两个正整数a,x 表示一次询问。 

【输出格式】 

共T行，每行一个正整数，表示答案。 

【样例输入】

3  5 6  7 2  2 998244353

【样例输出】

3  3  1

【样例解释】

 杨辉三角如下： 

第一行： 1  第二行： 1 1  第三行： 1 2 1  第四行： 1 3 3 1  第五行： 1 4 6 4 1  第六行：  1 5 10 10 5

这个三角的生成方式如下： 1. 第 行（ 是正整数）有 个数。 2. 记第 行从左到右数第 个数为 （ 都是正整数），则

可见前6 行的和为63 ,对5 取模后结果为3 。 前2 行的和为3 ,对 7取模后结果为3 。

【说明提示】

对于10% 的数据，满足 n<=5； 

对于20% 的数据，满足T=1,n<=50 ； 

对于40% 的数据，满足T<=10,n<=100； 

对于60% 的数据，满足n<=106 ； 

对于80% 的数据，满足N<=1018 ； 

对于100%的数据，满足 T<103,m<108,n<101000 保证 m为质数

1.问题描述及状态定义

数字三角形问题：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示：

从第一行开的数开始走，每次可以往下或右走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和最大?

【题目描述】

考虑冒泡排序的一种实现。

bubble-sort  (A[],  n)

>   round  =  0

>   while  A  is  not  sorted

>   >   round  :=  round  +  1

>   >   for  i  :=  1  to  n  -  1

>   >   >   if  (A[i]  >   A[i  +  1])

>   >   >   >   swap(A[i],  A[i  +  1])

求1  ..  n的排列中，有多少个排列使得A被扫描了K遍，亦即算法结束时round  ==  K。

答案模20100713输出。

【输入描述】

输入包含多组数据。每组数据为一行两个整数N，K。 

数据规模和约定

T  < =  10  ^  5。

1  < =  K  <   N  <   10  ^  6。

【输出描述】

【样例输入】

3  3 0  3 1  3 2

【样例输出】

1  3  2

1.方程求解

【描述】

输入正整数 a，b，c。

求有多少组 x 和 y 满足 a*x+b*y=c 。x 和 y 都是非负整数。

【输入】

一行，包含三个正整数 a，b，c，两个整数之间用单个空格隔开。

【输出】

满足 a*x+b*y=c 的 x 和 y 的组数。

【输入样例】

2 3 18

【输出样例】

4

【样例说明】

有以下 4 组 x 和 y 满足 2*x+3*y=18:

x=0,y= 6

x=3,y= 4

x=6 ,y=2

x=9,y= 0

【数据范围】

50%的数据，1<=a,b,c<=1000；

100%的数据，1<=a,b,c<=100000。

4.队列问题（lru.cpp）

【题目描述】

有一个大小为n的页面缓存队列，初始为空，当计算机访问页面时，若缓存队列没有该页面，则加入到缓存队列中，若队列已满，则将删除访问时间最远的页面。

有Q次询问，每次询问输入一个整型x,表示访问页面x。若缓存队列中有则输出yes,否则输出no。

【输入描述】

第一行，2个空格隔开正整数n,Q

以下Q行：每行是一个整型x。

【输出描述】

Q行，每行可能为yes或者no

【样例输入】

3 10  1  2  1  3  5  6  1  5  2  6

【样例输出】

no  no  yes  no  no  no  no  yes  no  no

【样例解释】

【数据范围】

60%的数据：n<=1000,Q<=1000；

100%的数据：n<=100000,Q<=100000

【题目描述】

任意给定一个正整数N(N≤100)，计算2的n次方的值。

【输入描述】

输入一个正整数N。

【输出描述】

输出2的N次方的值。

【样例输入】

5

【样例输出】

32