#P1604. 2023.09.25-ali-第三题-封狼居胥
2023.09.25-ali-第三题-封狼居胥
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
霍去病改革下的汉军骑兵,身披甲胄,手持长矛,以冲锋形态向匈奴军队进行无畏冲刺,这是汉荡平匈奴的一大成因。现在你置身广阔的草原,手下的骑兵和匈奴骑兵共n个人已然混作一团,但在霍将军看来,实际上只是一字排开。现在塔子模拟了一个游戏,你需要指挥骑兵作战。我们假设这一排人中有你的大汉的骑兵,也有匈奴的骑兵,每一次指挥,你有两种选择:
1.如果第i个位置是汉军骑兵的,并且i+1<n,第i+1个位置是匈奴骑兵,那么你可以指挥汉军骑兵将其消灭,在第i+1个位置将自动生成一个你的骑兵。(游戏嘛,never mind)
2.如果第i个位置是汉军骑兵的,并且i−1>0,第i−1个位置是匈奴骑兵,那么你可以指挥汉军骑兵将其消灭,在第i−1个位置将自动生成一个你的骑兵。(游戏嘛,never mind)
你必然可以调度过程中生成的你的骑兵!
如此看来,胜利是必然的,但是塔子出品,必属精品,你需要回答有多少种击杀顺序,可以把所有匈奴骑兵都消灭。
第一行一个整数n,表示骑兵的数量。 第二行一个字符串s,表示初始时哪些格子是汉军骑兵。如果第i个位置是汉军骑兵,那么si=1,否则si=0。1<n<105
输出一个整数,表示答案对 109+7 取模的结果
输入
5
01100
输出
3
说明
可能的击杀所有匈奴骑兵的顺序是,[0,3,4],[3,0,4],[3,4,0]
1s, 1024KiB for each test case.
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.