Count The Blocks

Count The Blocks 题目链接

思路

首先打表出来，发现了一个规律 \(num[1] = 10, num[2] = 180\)，这里的数组标记是反的

发现假定前 \(n - 1\)个num已经求得，我们可以得到

\(num[n] = n * 10^{n} - \sum \limits ^{n - 1} _{i = 1}(num[n - i] * (i + 1))\)

通过对上面的带入，我们可以求得 \(num[3] = 3000 - (num[2] * 2 + num[1] * 3) = 2610\)

于是我们貌似得到了一个\(O(n^2)\)的算法，想想能不能优化。

我们定义一个sum变量，其中记录的是\(\sum \limits ^{n - 1} _{i = 1} num[i] * (n - i)\)

再开一个前缀和数组，\(a[i] = \sum\limits ^{i} _{k = 1}num[k]\)，接下来我们每次的操作就可以变成线性的来更新sum变量，也就是\(\sum \limits ^{n - 1} _{i = 1}(num[n - i] * (i + 1))\)一坨东西。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 2e5 + 10;

ll num[N], a[N];

ll quick_pow(ll x, ll n) {
    ll ans = 1;
    while(n) {
        if(n & 1)   ans = (ans * x) % mod;
        n >>= 1;
        x = (x * x) % mod;
    }
    return ans;
}
int main() {
    int n;
    scanf("%d", &n);
    num[1] = 10; a[1] = 10;
    ll sum = 10;
    for(int i = 2; i <= n; i++) {
        sum += a[i - 1];
        num[i] = (((quick_pow(10, i) * i) % mod - sum ) % mod + mod) % mod;
        a[i] = (a[i - 1] + num[i]) % mod;
        sum = (sum + num[i]) % mod;
    }
    for(int i = n; i > 0; i--)
        printf("%lld ", num[i]);
    puts("");
    return 0;
}