当前位置:网站首页>Nine hours, nine people, nine doors problem solving Report
Nine hours, nine people, nine doors problem solving Report
2022-07-05 15:25:00 【wch(】
Nine hours, nine people, nine doors problem solving report
label : Dynamic programming , Number root
source : Cattle from
Their thinking :
Tree radical
The first is to solve the digital root , We can set our own function to simulate and calculate , You can also use a faster formula .
Digital roots have such properties :x+9 And x Several of them are the same , That is, one number plus 9 After that, the number of its roots remains unchanged . So count a The root of the tree is a Yes 9 The result after taking the mold .
Formula for finding number root :a The number of roots b = (a-1) % 9+1
Proof of the nature of tree roots :
(abcd)% 9 = (a * 1000+b * 100+c * 10+d) % 9
= a%9+b%9+c%9+d%9
=(a+b+c+d)%9
Dynamic programming ( knapsack )
First think about how the state shifts , Set the following array dp[i-1][j], Before presentation i People can open the first j The maximum number of combinations of doors , At this point, we consider adding another person , Just call me this person , How will the maximum number of combinations of each door change after joining me , We can divide the maximum number of combinations into three parts :
There is no one else : dp[i][a[i]]=1;
There are others without me :dp[i][j]=(dp[i][j]+dp[i-1][j])%M;
I have others :dp[i][(j+a[i]-1)%9+1]=(dp[i][(j+a[i]-1)%9+1]+dp[i-1][j])%M
Code implementation :
#include <iostream>
#include <stdio.h>
using namespace std;
int a[100500];
int dp[100500][10];
const int M=998244353;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=(a[i]-1)%9+1;
}
for(int i=1;i<=n;i++){
dp[i][a[i]]=1;
for(int j=1;j<=9;j++){
dp[i][j]=(dp[i][j]+dp[i-1][j])%M;
dp[i][(j+a[i]-1)%9+1]=(dp[i][(j+a[i]-1)%9+1]+dp[i-1][j])%M;
}
}
for(int i=1;i<=9;i++){
cout<<dp[n][i]<<" ";
}
return 0;
}
边栏推荐
- 社区团购撤城“后遗症”
- 计算中间件 Apache Linkis参数解读
- Common MySQL interview questions (1) (written MySQL interview questions)
- 美团优选管理层变动:老将刘薇调岗,前阿里高管加盟
- Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
- CPU design practice - Chapter 4 practical task 2 using blocking technology to solve conflicts caused by related problems
- Go learning ----- relevant knowledge of JWT
- Bugku's eyes are not real
- qt creater断点调试程序详解
- easyOCR 字符識別
猜你喜欢
I spring and autumn blasting-1
How can I quickly check whether there is an error after FreeSurfer runs Recon all—— Core command tail redirection
First PR notes
lvgl 显示图片示例
P6183 [USACO10MAR] The Rock Game S
MySQL之CRUD
B站做短视频,学抖音死,学YouTube生?
Visual task scheduling & drag and drop | scalph data integration based on Apache seatunnel
Ctfshow web entry command execution
数据库学习——数据库安全性
随机推荐
Optional parameters in the for loop
[JVM] operation instruction
MySQL之CRUD
Appium自动化测试基础 — APPium基础操作API(二)
Bugku easy_ nbt
Bugku's Ah Da
MySQL----函数
Cartoon: programmers don't repair computers!
lvgl 显示图片示例
Crud de MySQL
Hongmeng system -- Analysis from the perspective of business
Behind the ultra clear image quality of NBA Live Broadcast: an in-depth interpretation of Alibaba cloud video cloud "narrowband HD 2.0" technology
数学建模之层次分析法(含MATLAB代码)
Fr exercise topic - simple question
[12 classic written questions of array and advanced pointer] these questions meet all your illusions about array and pointer, come on!
NBA赛事直播超清画质背后:阿里云视频云「窄带高清2.0」技术深度解读
Bugku alert
如何将 DevSecOps 引入企业?
亿咖通科技通过ISO27001与ISO21434安全管理体系认证
mapper. Comments in XML files