【Codeforces 1327E】Count The Blocks
The Codeforces count blocks
2023-09-14 09:03:41 时间
题目链接
翻译
让你统计\(0\) ~ \(10^n-1\) 中长度为 \(len\) 的连续块的个数
题解
考虑长度为 \(len\) 的连续块的位置,有两种情况
- ①连续块紧接着开头或结尾,即
xxxx........
以及.......xxxx
这两种 - ②连续块在中间
....xxxx.....
对于第①种情况,开头或结尾的连续块有 \(10\) 种可能,而和这个连续块紧接着的一个单元(注意是单元而不是块),有 \(9\) 种可能,因为不能和这个块相同。
然后剩余 \(n-len-1\) 个单元随意放, 有 \(10^{n-len-1}\) 种可能。
有头尾 \(2\) 种,所以第①种情况对应了 \(2*10*9*10^{n-len-1}\)
第②种情况,和这个连续块(10种可能),左右相邻的两个单元只有 \(9\) 种可能,然后剩余 \(n-len-2\) 个位置随意放 \(10^{n-len-2}\),然后这个连续块在中间的话有
\(n-len-1\) 种放法(除了头尾),所以第二种情况就对应了 \(10*9*9*10^{n-len-2}*(n-len-1)\) 种方案。
注意 \(len=n\) 时特殊处理,答案为固定的 \(10\)
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD = 998244353;
const int N = 2e5;
int n;
LL _pow[N + 10];
int main(){
// freopen("C://1.cppSourceProgram//rush.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
//step5 算10^i
_pow[0] = 1;
for (int i = 1;i <= N; i++){
_pow[i] = _pow[i-1]*10%MOD;
}
cin >> n;
//step1 ite i
for (int i = 1;i < n; i++){
LL ans = 0;
//step2 在头尾的情况
ans = (ans + 10*9*2*_pow[n-i-1]%MOD)%MOD;
//step3 在中间的情况
ans = (ans + 10*9*9*_pow[n-i-2]%MOD*(n-i-1)%MOD)%MOD;
cout << ans <<" ";
}
//step4 len=n
cout << 10 << endl;
return 0;
}
相关文章
- SqlBulkCopy – The given value of type String from the data source cannot be converted to type
- Mysql 1290 - The MySQL server is running with the --secure-file-priv option
- 【Vue-Spring跨域Bug已解决】has been blocked by CORS policy: The value of the······
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-27605: Smart I/O failed as a handle could not be obtained to the cell “string” as the cell is not accessible. ORACLE 报错 故障修复 远程处理
- ORA-27611: Smart I/O failed due to a block corruption detected on the host. The block was received from cell “string”. disk: “string”, block: “string”, disk offset: “string” ORACLE 报错 故障修复 远程处理
- ORA-31128: The event handler calls cannot exceed the depth of string ORACLE 报错 故障修复 远程处理
- ORA-38407: The ADT associated with the attribute set already exists. ORACLE 报错 故障修复 远程处理
- ORA-39186: No tablespaces in the specified list exist. ORACLE 报错 故障修复 远程处理
- ORA-41662: number of primitive events in the composite event exceeds maximum limit ORACLE 报错 故障修复 远程处理
- ORA-46012: The value of the “privilege” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-48485: The file exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48486: The file [string] exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48489: The input exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48928: The predicate exceeds the max limit string ORACLE 报错 故障修复 远程处理
- ORA-13003: the specified range for a dimension is invalid ORACLE 报错 故障修复 远程处理
- ORA-14212: subpartition cannot be split along the specified high bound ORACLE 报错 故障修复 远程处理
- ORA-19035: Invalid select item of the query in newContextFromHierarchy() ORACLE 报错 故障修复 远程处理
- Codeforces 842A Kirill And The Game暴力,水详解编程语言
- PHP curl报错“Problem (2) in the Chunked-Encoded data”解决方案详解编程语言
- Unleashing the Power of MySQL and SQL AS(mysqlsqlas)
- Oracle Database: Tackling the Complexities of Nulls(nulloracle)
- MySQL 5.7.17:The Latest Upgrade of the Database System(mysql5.7.17)
- nUnlocking the Power of Oracle: Unlocking All Possibilities(oracleu)
- Exploring the Characteristics of Oracle Transactions(oracle事务的特性)
- Exploring the Dynamic Duo: The Power of Solr MongoDB Integration(solrmongodb)
- Exploring the Power of MongoDB: The Definitive Guide to Upgrading Arrays(mongodb更新数组)
- Mastering the Linux Environment with MC: A Comprehensive Guide(linux.mc)
- Exploring the World of MySQL: Understanding How to Query the Current Database(mysql查询当前库)
- Exploring the Possibilities of Running Linux on i686 Architectures(linuxi686)
- Exploring the Power of UML in Linux: A Practical Guide(linux下uml)
- Exploring the Impact of Oracle on the Career of Tech Entrepreneur He Ming(oracle何明)