首页 > 代码库 > BZOJ 3612 HEOI2014 平衡 递推
BZOJ 3612 HEOI2014 平衡 递推
题目大意:给定一个杠杆,一共2n+1个位置,每个上面有一个质点,求拿走k个质点后使杠杆仍然保持平衡的方案数 mod p的值
n<=1W k<=10
令f[n][m]表示n个数划分为m个互不相同的数且最大不超过k的数的方案数
如果最小的数是1 等价于将最下方一排砍掉的方案数 即f[n-m][m-1]
如果最小的数不是1 等价于将最下方一排砍掉的方案数 即f[n-m][m]
但是这样求出的是最大不超过k+1的方案数 因此我们还要减掉最大等于k+1的方案数
最大等于k+1的方案数等价于将最右一排砍掉后最大不超过k的方案数 即f[n-k-1][m-1]
故有f[n][m]=f[n-m][m]+f[n-m][m-1]-f[n-k-1][m-1]
于是我们分是否取走中间的质点两种情况讨论,每次枚举左右的力矩和,枚举左右拿走的质点数即可
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; int n,k,p; int f[M][15]; //f[n][m]表示将n划分成m个互不相同且最大不超过k的数的方案数 int main() { int T,i,j; f[0][0]=1; for(cin>>T;T;T--) { cin>>n>>k>>p; for(i=1;i<=n*k;i++) for(j=1;j<=k;j++) { f[i][j]=0; if(i>=j) f[i][j]=f[i-j][j]+f[i-j][j-1]; if(i>=n+1) f[i][j]-=f[i-n-1][j-1]; f[i][j]=(f[i][j]+p)%p; } int ans=0; for(i=1;i<=n*k;i++) for(j=0;j<=k;j++) ans+=f[i][j]*f[i][k-j],ans%=p; k--; for(i=0;i<=n*k;i++) for(j=0;j<=k;j++) ans+=f[i][j]*f[i][k-j],ans%=p; cout<<ans<<endl; } return 0; }
BZOJ 3612 HEOI2014 平衡 递推
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。