NOIP2016Day2第一题

80 阅读 0 评论 53 点赞

我是靠谱客的博主昏睡电源，最近开发中收集的这篇文章主要介绍NOIP2016Day2第一题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

给定n,m和k，对于所有的0 <= i <= n，0 <= j <= min(i,m)有多少对 (i,j)满足 Cji 是k的倍数。
输入输出格式
输入格式：
第一行有两个整数t,k，其中t代表该测试点总共有多少组测试数据，k的意义见【问题描述】。
接下来t行每行两个整数n,m，其中n,m的意义见【问题描述】。
输出格式：
t行，每行一个整数代表答案。
输入输出样例
输入样例#1：
1 2
3 3
输出样例#1：
1
输入样例#2：
2 5
4 5
6 7
输出样例#2：
0
7
说明
【样例1说明】
在所有可能的情况中，只有 C21=2 是2的倍数。

题解

其实 Cji 其实就是杨辉三角形的第i行第j列的那个数（我说的杨辉三角形是从第0行开始数，从第0列开始数）。
设 f 数组为储存杨辉三角形数组，那么我们用n2的时间预处理求一下f数组（对k去模），然后再求一下 g 数组（储存f[0][0]到f[i][j]这个矩阵中对k取模的个数），最后对于每个询问O(1)输出答案。