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为质数

【题目描述】

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

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

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

【题目描述】

求两个大的正整数相减的差。

【输入】

共2行，第1行是被减数a，第2行是减数b(a > b)。每个大整数不超过200位，不会有多余的前导零。

【输出】

一行，即所求的差。

【输入样例】

9999999999999999999999999999999999999

9999999999999

【输出样例】

9999999999999999999999990000000000000

【题目描述】

求两个不超过200位的非负整数的和。

【输入】

有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。

【输出】

一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

【输入样例】

22222222222222222222

33333333333333333333

【输出样例】

55555555555555555555

区间数位个数(digit.cpp)

【描述】

给定整数n和整数k,求出1～n中所有数的每一位数字中,出现数字k的次数。

【输入】

第一行是两个个整数n和k

【输出】

一个整数表示答案。

【样例输入输出】

【数据范围】

60%的数据：n<=1e6,1<=k<=9

80%的数据：n<=1e12,1<=k<=9