题解 | #九小时九个人九扇门#

A-九小时九个人九扇门

一眼DP，但DP水平不行，就先去签到了，然后回来乱写就过去了？

首先，随便算算可以发现13+14+15的根等于42的根（都是6），大胆假设a+b的根=a的根+b的根。

那么，对第i个人考虑：

1. 根为j的组合加上他的根f(a[i])可以变成一个根为f(j+f(a[i]))的组合。

2. 根为j的组合不加上他将保持原根。

3. 他自己作为一个新的组合。

可以得到状态转移方程如下：

dp[i][f(j + f(a[i]))] += dp[i - 1][j];
dp[i][j] += dp[i - 1][j];
dp[i][f(a[i])]++;

由于DP和组合数学都没学好，所以过的不明不白。

代码如下：

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define x first
#define y second
#define pb push_back
#define endl '\n'
  
using namespace std;
  
typedef long long LL;
typedef long double LD;
typedef pair<LL,LL> PII;
  
const int N=1e6+5;
const int M = 998244353;
 
LL n,m,T;
LL a[N];
LL b[N];
LL ans[N];
LL dp[N][20];
vector<int> ve[N];
 
LL f(LL a){
    while(a>=10){
        LL ans=0;
        LL t=a;
        while(t){
            ans+=t%10;
            t/=10;
        }
        a=ans;
    }
    return a;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=f(a[i]);
        b[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        dp[i][a[i]]=(dp[i][a[i]]+1)%M;;
        for(int j=1;j<=9;j++){
            dp[i][j]=(dp[i][j]+dp[i-1][j])%M;
            dp[i][f(j+a[i])]=(dp[i][f(j+a[i])]+dp[i-1][j])%M;
        }
    }
    for(int i=1;i<=9;i++){
        cout<<dp[n][i]<<" ";
    }
    return 0;
}