B3902 [NICA #3] 数计组数 题解

· · 题解

简单计数背包 DP。

令 f_i 为长度为 i 的合法数组有多少个。初始 f_0=1；假设要从 f_j 转移到 f_i，考虑中间 i-j 个数怎么填：显然只能填大于等于 i-j 的数且 i-j 至少出现一次（如果 i-j 不在 S 中那么无法转移），令 a_x 为大于等于 x 的数的种类，方案数即为 x=a_{i-j}^{i-j}-(a_{i-j}-1)^{i-j}。根据乘法原理，有转移 f_i=f_j\cdot x。

计算过程可以借助快速幂实现。a_x 可以用 std::lower_bound 预处理。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%p*a%p;
    a=a%p*a%p,b>>=1;
  }
  return r;
} // 快速幂
main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  vector<int> b(m),e(n+1),c(n+1),f(n+1);
  for(auto &i:b)if(cin>>i;i<=n)e[i]=1;
  for(int i=1;i<=n;i++)
    c[i]=m-(lower_bound(b.begin(),b.end(),i)-b.begin());
    // 二分预处理
  for(int i=f[0]=1;i<=n;i++)
    for(int j=0;j<i;j++)
      if(e[i-j])(f[i]+=f[j]*(qpow(c[i-j],i-j)-qpow(c[i-j]-1,i-j)+p)%p)%=p;
      // 进行转移
  cout<<f[n]<<endl;
  return 0;
}