九小时九个人九扇门

#includeusing namespace std;const int N = 1e5 + 10;const int mod = 998244353;typedef long long ll;int n;int a[N];int f[N][10];void solve() { cin >> n; for (int i = 1; i <= n ;i++) { cin >> a[i]; a[i] %= 9; } for (int i = 1; i<= n; i++) { (f[i][a[i]] += 1) %mod; for (int j = 0; j < 9; j++) { (f[i][j] += f[i - 1][j]) %=mod; (f[i][(j +a[i]) % 9] += f[i -1][j]) %=mod; } } for (int i =1; i<= 8; i ++) cout << f[n][i] << " "; cout << f[n][0] << endl;}int main () { int t; t = 1; while (t --) solve(); return 0;}

关键在于每个数的根为对9取模。 然后就可以转换为01背包问题 为什么没想出来，没往dp的方向想，甚至没有认出是01背包。01背包就是每个物品取或者不取。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。