題目描述

組合數表示的是從n個物品中選出m個物品的方案數。舉個例子，從（1,2,3) 三個物品中選擇兩個物品可以有（1,2),(1,3),(2,3)這三種選擇方法。根據組合數的定 義，我們可以給出計算組合數的一般公式：

其中n! = 1 × 2 × · · · × n

小蔥想知道如果給定n,m和k，對于所有的0 <= i <= n，0 <= j <= min(i,m)有多少對 (i,j)滿足是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說明】

在所有可能的情況中，只有是2的倍數。

【子任務】

終于開始填noip的坑了.

分析：其實對于組合數，我們有一個公式：c[i][j] = c[i-1][j-1] + c[i-1][j],但是如果n達到2000，這個數可能會超級大，于是蒟蒻的我在考場上寫高精度......其實完全不需要，既然要求mod k = 0的個數，那么我們可以利用公式(a + b) mod c == (a mod c + b mod c) mod c,然后每算出一個c，我們就能根據它是不是0來判斷它是不是k的倍數，那么如何求c[0][0]到c[n][m]整除k的個數呢？一般而言，求和要用到前綴和，本題要用到二維前綴和，sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + ok[i][j],優化一下時間，看到t很大，先預處理(2000,2000)的組合數即可.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <string>using namespace std;int t, k, n, m,ans[2010][2010],c[2010][2010],ok[2010][2010];void init() {c[0][0] = 1;for (int i = 1; i <= 2000; i++){c[i][0] = 1;for (int j = 1; j <= i; j++){c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;if (c[i][j] == 0)ok[i][j] = 1;}}for (int i = 1; i <= 2000; i++)for (int j = 1; j <= 2000; j++)ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + ok[i][j]; }int main() {scanf("%d%d", &t, &k);init();for (int i = 1; i <= t; i++){scanf("%d%d", &n, &m);printf("%d\n", ans[n][m]);}return 0; }

?

轉載于:https://www.cnblogs.com/zbtrs/p/7242568.html

總結

以上是生活随笔為你收集整理的noip2016 组合数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。