题意

https://vjudge.net/problem/AtCoder-2037

选一些数使得和的平均值等于a,问方案数。

思路

设dp[i][j]为选i个数和为j的方案数,如果当前选了x,那么dp[j+1][w+x]+=dp[j][w]。

令dp[0][0]=1,注意倒序遍历j

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=55;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll dp[N][N*N];
int main()
{
std::ios::sync_with_stdio(false);
int n,a;
cin>>n>>a;
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
for(int j=i-1;j>=0;j--)
for(int w=0;w<=N*j;w++)
{
dp[j+1][w+x]+=dp[j][w];
// cout<<j+1<<" "<<w+x<<" "<<dp[j+1][w+x]<<endl;
}
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=dp[i][i*a];
}
cout<<ans<<endl;
return 0;
}

  

最新文章

  1. CAS单点登录配置
  2. HDU5900
  3. ajax提交特殊字符的处理
  4. 爬虫再探实战(三)———爬取动态加载页面——selenium
  5. 【windows核心编程】DLL相关(2)
  6. 学习笔记之APACHE ANT
  7. 利用if else 判断方程有几个根
  8. 3D空间中射线与三角形的交叉检測算法
  9. javaWEB与JSP指令
  10. Win7+CentOS双系统(一)
  11. eclipse 代码 editor 界面出现奇怪符号解决
  12. linux上快速搭建宝塔面板来操作便捷功能
  13. mysql的某个数据库拒绝访问的问题
  14. skywalking学习之路---skywalking环境从零搭建部署
  15. 1.Python
  16. [TensorFlow] Introducing TensorFlow Feature Columns
  17. 作业二 —— 分布式版本控制系统Git的安装与使用
  18. List stream 对象 属性去重
  19. 我对Web开发的认识
  20. idea心得

热门文章

  1. R语言入门1:安装R和RStudio
  2. swoole2——Worker与TaskWorker进程
  3. 解决Python3.6.5+Django2.0集成xadmin后台点击添加或者内容详情报 list index out of range 的错误
  4. xadmin进行全局配置(修改模块名为中文以及其他自定义的操作步骤)
  5. bay——巡检RAC操作.txt
  6. java 内存溢出总结
  7. &lt;Stack&gt; (高频)394 ( 高频)224
  8. __format__
  9. DirectShow 进行视频预览和录制
  10. Zookeeper分布式锁实战