Nine hours, nine people, nine doors problem solving report

label ： Dynamic programming , Number root

Topic link

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;
}