題目鏈接
題目描述
思路
選取的序列a可能的貢獻有 0,1,2,3,…,n-1，
設a的貢獻為d，
貢獻為d的序列有 [1,…,1+d], [2,…,2+d]… (共有n-d個這樣的序列)
對貢獻為d的序列a進行分析，
如果a的第一位為v，最后一位就為v+d，(因為a為非遞減數列)
剩余m-2個地方需要填充，
問題就轉變為，將 [v,v+1,v+2,…,v+d] 中的m-2個數字(可以重復，但序列需要是非遞減數列)填入序列，求本質不同的序列個數，
用到的知識點為隔板法
舉例說明一下:
將[1,2,3]中的6個數字填入序列，求本質不同的序列(非遞減)個數，
設序列為[a,b,c,d,e,f]，將2個板子插入序列中，可以得到其中一個為[a,b|c,d,e|f]
將第一個隔板左邊的序列[a,b]視為[1,1]
將第一個隔板和第二個隔板之間的序列[c,d,e]視為[2,2,2]
將第二個隔板右邊的序列[f]視為[3]
如果[1,2,3]中每個數字至少挑出來一個的話，結果為
C
5
2
C^{2}_5
C52?
因為挑出來的個數可以為0，可以當做增加了3個可放置隔板的位置，結果為
C
5
+
3
2
C^{2}_{5+3}
C5+32?
如果不是很理解的話，可以將這個問題視為盒子問題來考慮，相當于將6個小球放在3個盒子里面，用2個隔板將小球分開，
如果每個盒子里面至少有一個小球的話，結果為
C
5
2
C^2_5
C52?(有5個地方可以放隔板)
如果盒子里面的小球個數可以為0的話，將原本盒子里面小球個數視為-1(至少一個就變成了可以是0個)，需要放置的小球個數就變成6+3了，結果為
C
5
+
3
2
C^2_{5+3}
C5+32?
AC的代碼
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7, mod = 998244353;
int fac[N];
// 快速冪
int power(int a, int b){
int res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
// 求逆元
int inv(int a){
/*
因為 x^(p-1) % p = 1(費馬小定理)
所以 [x^(p-2) * x] % p = 1
x^(p-2) 相當于 x 的逆元
*/
return power(a, mod - 2);
}
// 對階乘預處理
void f(){
fac[0] = 1;
fac[1] = 1;
for(int i = 2; i <= N; i++)
fac[i] = fac[i - 1] * i % mod;
}
// C^a_b
int C(int a, int b){
return fac[b] * inv(fac[b - a]) % mod * inv(fac[a]) % mod;
}
signed main(){
f();
int n, m;
cin>>n>>m;
int res = 0;
for(int d = 1; d <= n - 1; d++){
res += (n - d) * C(d, (m - 3) + (d + 1)) % mod * d % mod;
res = res % mod;
}
cout<<res;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263348.html
標籤：其他