P11616 [PumpkinOI Round 1] 瓦解题目背景时间把镜头带走 不假思索 回忆不放手题目描述你手上有一个长为nnn的数列aaa。小 Q 想让你将其分成不超过mmm段非空连续段且每段内数字严格单调递增。现在小 Q 想知道一共有几种划分方案。由于方案数可能很大你只需要告诉她方案数对998244353998244353998244353取模的结果。输入格式本题包含多组测试数据。输入的第一行包含一个整数TTT表示测试数据的组数。接下来包含TTT组数据每组数据格式如下第一行包含两个整数n,mn,mn,m分别表示数列长度和段数要求。第二行包含nnn个整数a1,a2…ana_1,a_2\dots a_na1​,a2​…an​。输出格式对于每组测试数据输出一行包含一个整数表示方案数对998244353998244353998244353取模的结果。输入输出样例 #1输入 #12 3 2 2 3 1 10 5 7 10 9 23 1 6 7 8 9 20输出 #11 29说明/提示样例解释对于第一组数据只有[2,3],[1][2,3],[1][2,3],[1]这一种方案。数据规模与约定本题采用捆绑测试。Subtask 00 pts样例。Subtask 110 pts∑n≤10\sum n\le 10∑n≤10。Subtask 220 pts∑n≤1000\sum n\le 1000∑n≤1000。Subtask 310 pts保证数列本身严格单调递增。Subtask 430 pts∑n≤106\sum n\le 10^6∑n≤106。Subtask 530 pts∑n≤107\sum n\le 10^7∑n≤107。对于所有数据保证1≤∑n≤107,1≤m≤n,1≤ai≤1091\le \sum n\le 10^7,1\le m\le n,1\le a_i\le 10^91≤∑n≤107,1≤m≤n,1≤ai​≤109。C实现#includebits/stdc.h#defineP998244353#defineintlonglongusingnamespacestd;intT,ans;intn,m,cnt;inta[10000007];intmul[10000007];intqpow(inta,intb){intans1;while(b){if(b1)ans(ans*a)%P;a(a*a)%P;b1;}returnans%P;}intC(intn,intm){return(mul[n]*(qpow((mul[m]*mul[n-m])%P,P-2)%P))%P;}signedmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinT;mul[0]1;for(inti1;i10000000;i){mul[i](mul[i-1]*i)%P;}while(T--){cinnm;cntans0;for(inti1;in;i){cina[i];if(a[i]a[i-1]){cnt;}}for(inticnt;im;i){ans(ansC((n-1)-(cnt),i-cnt))%P;}coutans\n;}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容