P5239 回憶京都（洛谷3月月賽T2）

題目描述

射命丸文在取材中發現了一個好玩的東西，叫做組合數。

組合數的定義如下：從n個不同元素中，任取m(m≤n)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合。所有組合的數量，就是組合數。

$\sum_{i=1}^n \sum_{j=1}^m C^i_j$，其中當i>j的時候，欽定$C^i_j$​為0

她也很快就算出來了，不過對自己的答案不是很充滿信心，是以你決定幫助她。然而沒事找事的她一下子算了q次對于不同的n,m的結果，是以這隻能勞煩你了。由于你不打算真正地幫助她，你無需把答案對998244353取模，也無需對64123取模，隻要告訴她對19260817取模之後的答案即可。

輸入輸出格式

輸入格式：

第一行輸入一個q，表示有q次詢問。

第二行開始，一共q行，每行兩個數字n,m，意思如題所示。

輸出格式：

一共q行，對于每一個詢問，都輸出一個答案。

資料範圍：n,m<=1000

solution

 容易想到預處理出楊輝三角, c[i][j]表示$c^j_i$ %mod，遞推公式是c[i][j]=c[i-1][j]+c[i-1][j-1]，注意處理c[i][0]=1;

這樣每次詢問是O(nm)，總的時間複雜度是O(qnm)，TLE3個點，需要優化

通過模拟發現，題目中要求的數的和實際上在楊輝三角中是一個矩形的區域，也就是右下角下标為c[m][n]

例如，當m=4,n=3時，就是矩形區域的和，是以隻需要維護一個二維字首和就行了

一個大坑：當預處理二維字首和時因為經過了取模，是以容易出現新的字首和為負數的情況，而我們希望得到的一定是個正數，是以每一項s[i][j]=(s[i][j]+mod)%mod;

因為這個坑WA了三個

code

#include<cstdio>
#include<iostream>
#include<cstring>
#define mod 19260817//咳咳 
#define maxn 1020
using namespace std;
long long s[maxn][maxn],ts[maxn][maxn];
int n,m,t,x,ans,tmp;
void init(int n)
{
    for(int i=0;i<=n;++i)
    {
        s[i][0]=1;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(j<=i) s[i][j]=(s[i-1][j]+s[i-1][j-1])%mod;//楊輝三角 
            
            ts[i][j]=(ts[i-1][j]+ts[i][j-1]-ts[i-1][j-1]+s[i][j]+mod/*關鍵*/)%mod;//二維字首和 
        }
        
    }
          
         
}
int main()
{
    scanf("%d",&t);
    init(1010);//預處理楊輝三角與字首和 
    for(int k=1;k<=t;++k)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n",ts[m][n]);
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/Liuz8848/p/10465826.html