当前位置:网站首页>Codeforces Round #732 (Div. 2) D. AquaMoon and Chess
Codeforces Round #732 (Div. 2) D. AquaMoon and Chess
2022-07-05 05:30:00 【solemntee】
First, let's consider the simpler case
1100000000000 1100000000000 1100000000000
hold 11 11 11 As a group , This group can move on the number axis , The situation of each group corresponds to one s t a t e state state
Extension , For a continuous string of odd length
000011111000000 000011111000000 000011111000000
You can know that there is l e n / 2 len/2 len/2 A mass of , When the number of the left and right groups of this continuous string is determined, this group leaves “1” The location is uniquely determined , Take the example above , You can know that if the two regiments are on the left, what remains is the rightmost 1 1 1, One on the left and one on the right are left in the middle 1 1 1……
Back to the topic , We find all the cliques in a string , Then the conclusion drawn from the above , When the position of the regiment is determined, it is left alone “1” Determine the location , So we only need to consider the position relationship of the Group .
The problem turns into 1 ∗ m 1*m 1∗m Space for n n n individual 1 ∗ 2 1*2 1∗2 Number of options for items . Just write a formula .
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll poww(ll a,ll b)
{
ll t=1;
while(b>1)
{
if(b%2==1)t=t*a%mod;
a=a*a%mod;
b/=2;
}
return t*a%mod;
}
ll poww1[100005],poww2[100005];
void init()
{
poww1[0]=1;
poww2[0]=1;
for(int i=1;i<=100000;i++)poww1[i]=poww1[i-1]*i%mod;
for(int i=1;i<=100000;i++)poww2[i]=poww2[i-1]*poww(i,mod-2)%mod;
// printf("%lld\n",poww2[3]);
}
char s[100005];
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
scanf("%s",s+1);
int cnt0=0,cnt=0,cnt2=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='0')cnt0++;
if(s[i]=='1')cnt++;
if(s[i]=='0')
{
cnt2+=cnt/2;
cnt=0;
}
}
cnt2+=cnt/2;
printf("%lld\n",poww1[cnt0+cnt2]*poww2[cnt0]%mod*poww2[cnt2]%mod);
}
return 0;
}
边栏推荐
- Zzulioj 1673: b: clever characters???
- Reflection summary of Haut OJ freshmen on Wednesday
- Animation scoring data analysis and visualization and it industry recruitment data analysis and visualization
- lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
- Codeforces round 712 (Div. 2) d. 3-coloring (construction)
- 一个新的微型ORM开源框架
- [轉]: OSGI規範 深入淺出
- YOLOv5添加注意力機制
- SDEI初探-透过事务看本质
- [allocation problem] 455 Distribute cookies
猜你喜欢
【Jailhouse 文章】Look Mum, no VM Exits
sync. Interpretation of mutex source code
Sword finger offer 53 - ii Missing numbers from 0 to n-1
Yolov5 ajouter un mécanisme d'attention
Web APIs DOM节点
Pointnet++ learning
Service fusing hystrix
Sword finger offer 58 - ii Rotate string left
[轉]: OSGI規範 深入淺出
利用HashMap实现简单缓存
随机推荐
Sword finger offer 53 - ii Missing numbers from 0 to n-1
Codeforces round 712 (Div. 2) d. 3-coloring (construction)
过拟合与正则化
sync.Mutex源码解读
Little known skills of Task Manager
注解与反射
剑指 Offer 53 - I. 在排序数组中查找数字 I
【Jailhouse 文章】Look Mum, no VM Exits
Using HashMap to realize simple cache
[merge array] 88 merge two ordered arrays
Haut OJ 1245: large factorial of CDs --- high precision factorial
Pointnet++学习
YOLOv5-Shufflenetv2
剑指 Offer 09. 用两个栈实现队列
The present is a gift from heaven -- a film review of the journey of the soul
Improvement of pointnet++
[to be continued] [UE4 notes] L3 import resources and project migration
[interval problem] 435 Non overlapping interval
一个新的微型ORM开源框架
Demonstration of using Solon auth authentication framework (simpler authentication framework)