Solution -「ARC 110E」Shorten ABC
2024-10-16 02:29:36
\(\mathcal{Description}\)
Link.
给定长度为 \(n\),包含 A
, B
, C
三种字符的字符串 \(S\),定义一次操作为将其中相邻两个不相同的字符替换为字符集中不同于这两个字符的另一种字符。求任意次操作后得到的不同字符串个数,答案对 \(10^9+7\) 取模。
\(n\le10^6\)。
\(\mathcal{Solution}\)
我们希望探究此种替换操作的结合性,trick 为将字符集替换为数字集,将操作表达为数字间的运算。对于本题,令 A
, B
, C
为 \(1,2,3\),那么替换操作等价于将相邻两数替换为其异或和,于是就能预处理前缀异或和来求出一段区间操作后的结果。
接下来就能 DP 啦,令 \(f(i)\) 表示 \(S\) 前 \(i\) 个字符构成串的答案,枚举操作得到的串的下一个字符即可转移。最终答案为所有满足原串中后缀异或和为 \(0\) 的 \(f(i)\) 之和。
\(\mathcal{Code}\)
/* Clearink */
#include <cstdio>
#define rep( i, l, r ) for ( int i = l, rpbound##i = r; i <= rpbound##i; ++i )
#define per( i, r, l ) for ( int i = r, rpbound##i = l; i >= rpbound##i; --i )
const int MAXN = 1e6, MOD = 1e9 + 7;
int n, f[MAXN + 5], sum[MAXN + 5], nxt[MAXN + 5][4];
char s[MAXN + 5];
inline void addeq ( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD, 0 ); }
int main () {
scanf ( "%d %s", &n, s + 1 );
bool flg = false;
rep ( i, 1, n ) if ( ( flg = s[i] != s[1] ) ) break;
if ( !flg ) return puts ( "1" ), 0;
rep ( i, 1, n ) sum[i] = sum[i - 1] ^ ( s[i] - 'A' + 1 );
rep ( j, 0, 3 ) nxt[n][j] = n + 1;
per ( i, n, 1 ) {
rep ( j, 0, 3 ) nxt[i - 1][j] = nxt[i][j];
nxt[i - 1][sum[i]] = i;
}
f[0] = 1;
int ans = 0;
rep ( i, 0, n - 1 ) {
rep ( j, 0, 3 ) if ( sum[i] ^ j ) {
addeq ( f[nxt[i][j]], f[i] );
}
if ( sum[i + 1] == sum[n] ) addeq ( ans, f[i + 1] );
}
printf ( "%d\n", ans );
return 0;
}
最新文章
- Model-View-ViewModel for iOS [译]
- asp.net/html清理页面缓存的方法
- android 点击屏幕关闭 软键盘
- response content-type json
- gulp-webpack工程化实现electron
- 走进AngularJs(七) 过滤器(filter) - 吕大豹
- HTML、CSS、JS、PHP 的学习顺序~(零基础初学者)
- AP模块发票过账标记为否检查方法
- DHCP的主要知识点
- nginx conf_ctx ****
- centos7.4安装redis
- 全面理解Java内存模型(JMM)及volatile关键字
- JDB调试
- HDU 3376
- 判断颜色信息-RGB2HSV(opencv)
- .NET在IE10下的回传BUG修复
- bzoj千题计划134:bzoj3124: [Sdoi2013]直径
- eclipse启动报错 Problems occurred when invoking code from plug-in: ";org.eclipse.jface";
- 查看 page页面某一个属性在 web ui 中的位置。
- geotools中泰森多边形的生成
热门文章
- Python之路 - Day4 - Python基础4 (新版)
- root安装jdk其它用户授权
- sql审核-避免离线sql导致的db集群故障
- No shutdown animation in the electricity display only 1%
- python闭包函数&;装饰器
- 【小实验】rust的数组是在堆上分配还是在栈上分配的呢?
- 【记录一个问题】用ndk的gcc命令行无法编译C++11的lambda等语法的代码
- Chrome本地跨域请求设置,实现HTML模板页
- 基于World Wind的数据可视化插件
- Vue3 框架基础随笔 (一)