2022牛客寒假算法基础集训营1 ABCDEFGHIJKL

A.九小时九个人九扇门 思路

首先观察数根的性质，令 R ( x ) R(x) R(x)表示数字 x x x的数字根，那么有 R ( a ) + R ( b ) = R ( a + b ) R(a) + R(b) = R(a + b) R(a)+R(b)=R(a+b)，根据这个性质：

• 设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个人可以组合出 j j j的方案数

• 第 i i i个人被加入方案时：第 i − 1 i-1 i−1个人组合出 j j j的状态下可以向第 i i i个人组合出 j + R ( a [ i ] ) j + R(a[i]) j+R(a[i])的状态转移，也就是 d p [ i ] [ j + R ( a [ i ] ) ] + = d p [ i − 1 ] [ j ] dp[i][j + R(a[i])] += dp[i - 1][j] dp[i][j+R(a[i])]+=dp[i−1][j]

• 第 i i i个人不加入方案时：第 i − 1 i-1 i−1个人组合出 j j j的状态下可以向第 i i i个人组合出 j j j的状态转移，也就是 d p [ i ] [ j ] + = d p [ i − 1 ] [ j ] dp[i][j] += dp[i - 1][j] dp[i][j]+=dp[i−1][j]

• 注意从 0 0 0开始枚举，因为第 i i i个人本身可以作为一种方案存在

求数根可以直接应用性质：模 9 9 9取根，注意 9 9 9的倍数直接赋 9 9 9，然后根据以上分析写即可。

Accepted Code

#include 
using namespace std;

const int N = 1e5 + 10, MOD = 998244353;
int dp[N][15], a[N];

inline int get(int x){
    if(x > n;
    dp[0][0] = 1;
    for(int i = 1; i > num;
        a[i] = get(num);
    }
    for(int i = 1; i