CF1327E Count The Blocks（组合数学，计数）

佚名 4年前 (2020-04-24) 算法 892人围观抢沙发百度已收录

Count The Blocks

思路：题目可以理解为求长度为x（每个字符相同）的块有多少个。我们可以把这些字符合并成一个块，假设这个块的长度为m,这样总长度n = n - m + 1.这个块两边不能有相同的字符。那么分情况讨论：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

假设n = 4, x = 2,那么 n = 4 - 2 + 1 = 3.

①块在两边：

10 * 9 * 10 * 2（最左边和最右边）

②块在中间

9 * 10 * 9 * （n - 2）（除去两边的位置）

这样我们可以推出公式可以：

①情况： 9 * 10^(n - 1) * 2

②情况： 9 * 9 * 10^(n - 2) * (n - 2)

长度为x的块情况下，n为对应的剩余长度，则cnt = ① + ②，这样我们可以先预处理出10^(0~n)的答案再去求x = 1~n的个数。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <functional>
 5 #include <set>
 6 #include <vector>
 7 #include <queue>
 8 #include <cstring>
 9  
10 using namespace std;
11  
12 #define ll long long
13 #define pb push_back
14 #define fi first
15 #define se second
16  
17 const int N = 2e5 + 10;
18 const int INF = 1e9;
19 const int MAX_DIS = 2e6;
20 const ll MOD = 998244353;
21 
22 int _case = 0;
23 
24 void solve(){
25     int n;
26     cin >> n;
27     vector<ll > a(n + 1);
28     a[0] = 1;
29     for(int i = 1; i <= n; ++i) a[i] = (a[i - 1] * 10) % MOD;
30     vector<ll > ans(n + 1);
31     ans[1] = 10; ans[2] = 180;
32     for(int i = 3; i <= n; ++i) 
33         ans[i] =
34               ((a[i - 2] * 81 * (i - 2)) % MOD + (a[i - 1] * 9 * 2) % MOD ) % MOD;
35     
36         for(int i = n; i >= 1; --i) cout << ans[i] << " ";
37     cout << endl;
38 } 
39 
40 int main(){
41     
42     ios::sync_with_stdio(false);
43     cin.tie(0);
44     cout.tie(0);
45     solve();
46     
47     return 0;
48 }