当前位置:网站首页>D - I Hate Non-integer Number(背包dp)
D - I Hate Non-integer Number(背包dp)
2022-08-01 13:22:00 【Harris-H】
D - I Hate Non-integer Number(背包dp)
一开始想到dp,但是开了个三维数组不知道怎么转移。
实际上枚举选取的个数 i i i。
然后遍历 a a a,枚举当前选了 j j j个,模 i i i的余数为 k k k,这里用背包思想简化一维。
// Problem: D - I Hate Non-integer Number
// Contest: AtCoder - AtCoder Beginner Contest 262
// URL: https://atcoder.jp/contests/abc262/tasks/abc262_d
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// Date: 2022-07-31 23:51:13
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=105,M=2e4+5,inf=0x3f3f3f3f,mod=998244353;
const int hashmod[4] = {
402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
template <typename T> //x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
if(x>y) x=y;
}
ll a[N];
ll f[N][N];
ll ans;
int main(){
int n;cin>>n;
rep(i,1,n) cin>>a[i];
rep(i,1,n){
mst(f,0);
f[0][0]=1;
for(int u=1;u<=n;u++)
for(int j=i;j;j--)
for(int k=0;k<i;k++){
(f[j][(k+a[u])%i]+=f[j-1][k])%=mod;
}
(ans+=f[i][0])%=mod;
}
cout<<ans;
return 0;
}
边栏推荐
猜你喜欢
MCU开发是什么?国内MCU产业现状如何
Efficiency tools to let programmers get off work earlier
50W+小程序开发者背后的数据库降本增效实践
PAT 1162 Postfix Expression(25)
How do we do full-link grayscale on the database?
The basic knowledge of scripting language Lua summary
PAT 1163 Dijkstra Sequence(30)
PAT1166 Summit(25)
MySQL调优
Windows 安装PostgreSQL
随机推荐
高仿项目协作工具【Worktile】,从零带你一步步实现组织架构、网盘、消息、项目、审批等功能
SQL函数 SQUARE
HMS Core音频编辑服务音源分离与空间音频渲染,助力快速进入3D音频的世界
SAP ABAP OData 服务如何支持创建(Create)操作试读版
芝加哥丰田技术学院 | Leveraging Natural Supervision for Language Representation Learning and Generation(利用自然监督进行语言表示学习和生成)
How to Integrate Your Service Registry with Istio?
AtCoder Beginner Contest 261 D - Flipping and Bonus
全链路灰度在数据库上我们是怎么做的?
What Can Service Mesh Learn from SDN?
iPhone难卖,被欧洲反垄断的服务业务也难赚钱了,苹果的日子艰难
计算器:中缀表达式转后缀表达式
sql is not null 优化(oracle语句索引优化)
魔众短链接系统 v3.9.0
响应式2022英文企业官网源码,感觉挺有创意的
sql中常用到的正则表达
如何使用OpenCV测量图像中物体之间的距离
一文带你彻底厘清 Isito 中的证书工作机制
Do wildcard SSL certificates not support multiple domains?
Service Mesher Meetup 成都站:Service Mesh是下一代SDN吗?
什么是元编程