ssh实训做网站代码下载,wordpress 到顶插件,网站建设优化服务渠道,沂源做网站正题
题目链接:https://www.luogu.com.cn/problem/P3643 题目大意
求有多少个nnn个数的序列xxx满足#xff0c;xi∈{0}∪[ai,bi]x_i\in \{0\}\cup[a_i,b_i]xi∈{0}∪[ai,bi]且非000数递增。 解题思路
会发现ai,bia_i,b_iai,bi很大不能太暴力的将第二维的dpdpdp设…正题
题目链接:https://www.luogu.com.cn/problem/P3643 题目大意
求有多少个nnn个数的序列xxx满足xi∈{0}∪[ai,bi]x_i\in \{0\}\cup[a_i,b_i]xi∈{0}∪[ai,bi]且非000数递增。 解题思路
会发现ai,bia_i,b_iai,bi很大不能太暴力的将第二维的dpdpdp设为上一个选了的数是多少。
可以考虑离散化会将整个数轴分成最多2n−12n-12n−1个区间但是这样我们就不能确定上个数字具体在哪里了。nnn比较小所以我们可以考虑一种比较合理的方法就先确定这个区间中有多少个数然后再用组合数算出这个区间的方案。
设fi,jf_{i,j}fi,j表示到第iii个数并且这个数不是000在第jjj个区间时的方案若从fk,l(ki,lj)f_{k,l}(ki,lj)fk,l(ki,lj)转移过来也就是在[k1,i][k1,i][k1,i]的数要么在jjj这个区间内要么是000。若区间jjj的长度为lenlenlen[k1,i][k1,i][k1,i]中的数能选到区间jjj的数的个数为ccc当然iii一定要能选到此时的方案数应该是(lencc)\binom{lenc}{c}(clenc)。
可以理解为我们要在[0,len][0,len][0,len]这个范围内选出ccc个数使得非000数递增那么我们让前面是1∼len1\sim len1∼len然后在最后面放ccc个000此时选到000的位置就表示这个位置是000否则就按选择的非零数填到后面没有选择的000的位置。
那么现在就有转移 fi,j∑k0i−1(lencc)∑l0j−1fk,lf_{i,j}\sum_{k0}^{i-1}\binom{lenc}{c}\sum_{l0}^{j-1}f_{k,l}fi,jk0∑i−1(clenc)l0∑j−1fk,l 后面那个前缀和优化一下时间复杂度就能到O(n3)O(n^3)O(n3)了写起来细节有一点多。 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1010,P1e97;
ll n,a[N],b[N],p[N],inv[N],fac[N];
ll ans,f[N][N],g[N][N];
int main()
{// printf(%d,sizeof(f)20);scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,a[i],b[i]);p[i]a[i];b[i];p[in]b[i];}inv[1]1;for(ll i2;in;i)inv[i]P-(P/i)*inv[P%i]%P;inv[0]1;for(ll i1;in;i)inv[i]inv[i-1]*inv[i]%P;sort(p1,p12*n);ll munique(p1,p12*n)-p-1;for(ll i0;im;i)g[0][i]1;for(ll i1;in;i){for(ll j1;jm;j){if(p[j]a[i]p[j1]b[i]){ll lp[j1]-p[j];fac[0]1;for(ll k1;kn;k)fac[k]fac[k-1]*(lk-1)%P;for(ll ki-1,c1;k0;k--){(f[i][j]fac[c]*inv[c]%P*g[k][j-1]%P)%P;if(p[j]a[k]p[j1]b[k])c;}}g[i][j](g[i][j-1]f[i][j])%P;}}for(int i1;in;i)(ansg[i][m-1])%P;printf(%lld\n,ans);return 0;
}
