1566: [NOI2009]管道取珠 - BZOJ
2024-08-22 17:59:54
Description
Input
第一行包含两个整数n, m,分别表示上下两个管道中球的数目。 第二行为一个AB字符串,长度为n,表示上管道中从左到右球的类型。其中A表示浅色球,B表示深色球。 第三行为一个AB字符串,长度为m,表示下管道中的情形。
Output
仅包含一行,即为 Sigma(Ai^2) i从1到k 除以1024523的余数。
Sample Input
2 1
AB
B
Sample Output
5
HINT
样例即为文中(图3)。共有两种不同的输出序列形式,序列BAB有1种产生方式,而序列BBA有2种产生方式,因此答案为5。
【大致数据规模】
约30%的数据满足 n, m ≤ 12;
约100%的数据满足n, m ≤ 500。
这个思路太好了,神了
我们要求Ai的平方,就是要求效果相同的取出序列两两组合有多少种方案
相当于有两个人在做这个游戏,你要求他们两个输出序列相同的方案数
这样问题就转化成了求相同的取出序列有多少个,设f[x,y,x',y']表示第一行取到x个,第二行取到y个和第一行取到x'个,第二行取到y'个相同的序列有多少个
最后答案就是f[n,m,n,m],因为x+y=x'+y'所以我们可以减少一维变成f[x,y,x']还可以用滚动数组优化空间(貌似bzoj上给的空间够大,直接开不会爆)
const
maxn=;
h=;
var
f:array[..,-..maxn,-..maxn]of longint;
a,b:array[..maxn]of char;
n,m,xi,yi:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure main;
var
i,j,l:longint;
begin
readln(n,m);
for i:= to n do read(a[i]);readln;
for i:= to m do read(b[i]);
f[,,]:=;xi:=;yi:=;
for l:= to n+m do
begin
for i:= to min(n,l) do
for j:= to min(n,l) do
begin
if a[i]=a[j] then inc(f[yi,i,j],f[xi,i-,j-]);
if b[l-i]=b[l-j] then inc(f[yi,i,j],f[xi,i,j]);
if a[i]=b[l-j] then inc(f[yi,i,j],f[xi,i-,j]);
if b[l-i]=a[j] then inc(f[yi,i,j],f[xi,i,j-]);
f[yi,i,j]:=f[yi,i,j]mod h;
end;
xi:=xi xor ;yi:=yi xor ;
fillchar(f[yi],sizeof(f[yi]),);
end;
writeln(f[xi,n,n]);
end; begin
main;
end.
最新文章
- C#串口通信—向串口发送数据,同步接收返回数据
- eclispe常用快捷键
- FreeMarker标签介绍
- python分割字符串split,filter函数用法
- 转 MYSQL学习(一)
- 为benchmarksql的PostgreSQL java驱动进行升级
- N层电梯只停一层情况下,求所有人爬楼层数最少
- Tcp/Ip协议族简单解读及网络数据包/报/帧数据格式及封装及解包;
- AE + GDAL实现影像按标准图幅分割(上)
- 【BZOJ3530】数数(AC自动机,动态规划)
- Step by Step 真正从零开始,TensorFlow详细安装入门图文教程!帮你完成那个最难的从0到1
- studio中碰到的jni问题:java.lang.UnsatisfiedLinkError
- Java+selenium chrome 常见的问题WebDriverException: unknown error: call function result missing &#39;value&#39;
- Confluence 6 在 Apache 或者系统级别阻止垃圾
- centos安装VirtualBox增强包VBoxGuestAdditions
- kafka 消息系统
- 2018-2019-2 网络对抗技术 20165332 Exp2 后门原理与实践
- IIS解决上传文件大小限制
- css中的三种基本定位机制
- hdu刷题2
热门文章
- VBA表格单元格替换文字
- 使用nodejs引用socket.io做聊天室
- c#判断网络连接状态示例代码
- PHP 把GBK编码转换为UTF8
- [div+css布局]命名规则
- C# 页面抓取类
- Java 控制台执行带自定义包定义的类,出现“Exception in thread ";main"; java.lang.NoClassDefFoundError: ConnectSQLServer (wrong name: sine/ConnectSQLServer)”
- Oracle 11g Windows 迁移至 Linux
- perl实现awk的功能
- python: 命令选项及归类