题解：P16804 [蓝桥杯 2026 国 Python A] 键盘失灵

liangxiao2011 · 2026-07-21 10:58:58 · 题解

题解：P16804 [蓝桥杯 2026 国 Python A] 键盘失灵

题意简述

求由 26 个小写字母组成、长度为 n = 20260606 的所有字符串中，存在至少连续 k = 2026 个相同字母的字符串数量，对 998244353 取模。

思路

我们发现直接计算“存在连续 2026 个相同字母”的方案数比较困难，需要考虑的情况特别多，因此考虑正难则反，用总方案数减去不合法方案数，答案为 26^n - dp_n。

其中 dp_n 表示长度为 n 且不存在连续 2026 个相同字母的字符串数量。

递推式

设 dp_i 为长度为 i 的、不存在连续 2026 个相同字母的合法字符串数量。

考虑如何从 dp_{i-1} 转移到 dp_i：

当 i \le 2025 时，由于此时字符串长度一定小于 2026，因此所有状态均合法。
当 i \ge 2026 时，考虑在不会卡死的字符串后添加新字符，最多可以连续添加 2025 个。为了防止卡死，只能添加与末尾字符不同的字符，即 25 种新字符。

因此，转移式为：

dp_i = \begin{cases} 26^{i} & i \le 2025 \\ 25 \sum_{j = i - 2025}^{i-1} dp_j & i \ge 2026 \end{cases}

优化

由于枚举 i - 2025 到 i - 1 会导致时间复杂度过高，因此我们用滑动窗口的思想，使用前缀和来维护区间 [i - 2025,i-1] 内 dp_i 的总和。

最终答案为 338867718。

代码实现

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define ft first
#define sc second
#define P pair<int,int>
#define el putchar('\n')
using namespace std;
template<typename T>void read(T& value_name){if(typeid(T)==typeid(int) || typeid(T)==typeid(long long) || typeid(T)==typeid(unsigned int) || typeid(T)==typeid(unsigned long long)){T result_read=0,flag_of_symbol=1;int char_value=getchar();while(char_value<'0' || char_value>'9'){if(char_value=='-'){flag_of_symbol=-1;}char_value=getchar();}while(char_value>='0' && char_value<='9'){result_read*=10;result_read+=char_value-'0';char_value=getchar();}value_name=result_read*flag_of_symbol;}else if(typeid(T)==typeid(char)){char c=getchar();while(isspace(c)){c=getchar();}value_name=c;}else{cin>>value_name;}}
template<typename T1,typename... T>void read(T1& value_name1, T&... value_name){read(value_name1);read(value_name...);}
void read_string(string& string_name){string_name="";char char_value=getchar();while(char_value!=EOF&&isspace(char_value)){char_value=getchar();}while(char_value!=EOF&&!isspace(char_value)){string_name+=char_value;char_value=getchar();}}
template<typename T_size,typename T_arr> void read_array(T_size array_lenth,T_arr& array_name,int flag_idx=0){for(T_size i=flag_idx;i<array_lenth+flag_idx;i++){read(array_name[i]);}}
template<typename T_size,typename T_arr,typename T_read> void fread_array(T_size array_lenth,T_arr& array_name,T_read func,int flag_idx=0){for(T_size i=flag_idx;i<array_lenth+flag_idx;i++){func(array_name[i]);}}
template<typename T>void write(T value_name){if(typeid(T)==typeid(int) || typeid(T)==typeid(long long) || typeid(T)==typeid(unsigned int) || typeid(T)==typeid(unsigned long long)){if(value_name<0 && (typeid(T)==typeid(int) || typeid(T)==typeid(long long))){putchar('-');value_name=-value_name;}if(value_name<10){putchar(value_name+'0');}else{write(value_name/10);putchar((value_name%10)+'0');}}else if(typeid(T)==typeid(char) || typeid(T)==typeid(unsigned char)){putchar(value_name);}else{cout<<value_name;}}
template<typename T1,typename... T>void write(T1 value_name1, T... value_name){write(value_name1);write(value_name...);}
template<typename T_size,typename T_arr> void write_array(T_size array_lenth,T_arr array_name,char space_char,int flag_idx=0,bool is_endl=1){for(T_size i=flag_idx;i<array_lenth+flag_idx;i++){write(array_name[i],' ');}if(is_endl){putchar('\n');}}
template<typename T_size,typename T_arr,typename T_write> void fwrite_array(T_size array_lenth,T_arr array_name,T_write func,char space_char,int flag_idx=0,bool is_endl=1){for(T_size i=flag_idx;i<array_lenth+flag_idx;i++){func(array_name[i]);if(i!=array_lenth+flag_idx-1){putchar(space_char);}}if(is_endl){putchar('\n');}}
void write_string(string string_name,bool is_endl=1){for(int i=0;i<string_name.size();i++){putchar(string_name[i]);}}
template<typename T>T mins(T value_name){return value_name;}
template<typename T,typename... Ts>T mins(T value_name1,T value_name2,Ts... value_name){T tmp=min(value_name1,value_name2);return mins(tmp,value_name...);}
template<typename T>T maxs(T value_name){return value_name;}
template<typename T,typename... Ts>T maxs(T value_name1,T value_name2,Ts... value_name){T tmp=max(value_name1,value_name2);return maxs(tmp,value_name...);}
int ksm(int a,int b,int p){int res=1;while(b){if(b&1) res=res*a%p;a=a*a%p;b>>=1;}return res%p;}
//缺省源 

const int mod=998244353;
int dp[21000000];
int sum;//用于前缀和维护

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=2025;i++){
        dp[i]=ksm(26,i,mod);
        (sum+=dp[i])%=mod;
    }
    for(int i=2026;i<=20260606;i++){
        dp[i]=25*sum%mod;
        sum=(sum+dp[i]-dp[i-2025]+mod)%mod;
    }
    write((ksm(26,20260606,mod)-dp[20260606]+mod)%mod);
    return 0;
}