成都网站设计学校,asp古典网站源码,优的深圳网站设计公司,信息免费发布平台正题 题目大意
求有多少个长度为nnn且由1∼p1\sim p1∼p组成的序列满足在求最大值时交换了kkk次。 解题思路
考虑dpdpdp预处理。
用fi,j,kf_{i,j,k}fi,j,k表示长度为iii#xff0c;最大的数是jjj#xff0c;交换了kkk次
显然有fi,j,kfi−1,p,k−1fi−1,j,k∗j(pj)f…正题 题目大意
求有多少个长度为nnn且由1∼p1\sim p1∼p组成的序列满足在求最大值时交换了kkk次。 解题思路
考虑dpdpdp预处理。
用fi,j,kf_{i,j,k}fi,j,k表示长度为iii最大的数是jjj交换了kkk次
显然有fi,j,kfi−1,p,k−1fi−1,j,k∗j(plt;j)f_{i,j,k}f_{i-1,p,k-1}f_{i-1,j,k}*j(plt;j)fi,j,kfi−1,p,k−1fi−1,j,k∗j(pj) 对于fi−1,p,k−1f_{i-1,p,k-1}fi−1,p,k−1我们可以前缀和优化到O(npk)O(npk)O(npk)
然后我们要考虑最大的不一定是ppp所以ans∑i1pfn,i,kans\sum _{i1}^p f_{n,i,k}ansi1∑pfn,i,k
时间复杂度O(NPK∑p)O(NPK\sum p)O(NPK∑p) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll XJQ1e97;
ll t,f[110][310][110],n,k,p,ans,sum[310][110];
int main()
{scanf(%lld,t);for(ll i1;i300;i)f[1][i][1]1;for(ll j1;j300;j)sum[j][1](sum[j-1][1]f[1][j][1])%XJQ; for(ll i2;i100;i){for(ll j1;j300;j)for(ll k1;kmin(i,j);k)f[i][j][k](f[i-1][j][k]*j%XJQsum[j-1][k-1])%XJQ;memset(sum,0,sizeof(sum));for(ll j1;j300;j)for(ll k1;ki;k)sum[j][k](sum[j-1][k]f[i][j][k]%XJQ);}while(t--){scanf(%lld%lld%lld,n,k,p);p;ans0;for(ll i1;ik;i)ans(ansf[n][i][p])%XJQ;printf(%lld\n,ans);}
}
