度度熊保护村庄
Accepts: 13
Submissions: 488
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
哗啦啦村袭击了喵哈哈村！
度度熊为了拯救喵哈哈村，带着自己的伙伴去救援喵哈哈村去了！度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地，牢牢的守住了喵哈哈村。
但是度度熊发现，这是一场旷日持久的战斗，所以度度熊决定要以逸待劳，保存尽量多的体力，去迎战哗啦啦村的战士。
于是度度熊决定派尽量多的人去休息，但是同时也不能松懈对喵哈哈村的保护。
换句话而言，度度熊希望尽量多的人休息，而且存在一个包围圈由剩下的人组成，且能够恰好的包围住喵哈哈村的所有住房（包括边界）。
请问最多能让多少个人休息呢？
Input
本题包含若干组测试数据。
第一行一个整数n，表示喵哈哈村的住房数量。
接下来n行，每行两个整数(x1[i],y1[i])，表示喵哈哈村的住房坐标。
第n+1行一个整数m，表示度度熊的士兵数量。
接下来m行，每行两个整数(x2[i],y2[i])，表示度度熊伙伴的坐标。
满足:
1<=n,m<=500
-10000<=x1[i],x2[i],y1[i],y2[i]<=10000
Output
请输出最多的人员休息的数目。
如果无法保护整个村庄的话，输出"ToT"
Sample Input
2
1 1
2 2
4
0 0
0 4
4 2
4 0
1
1 1
2
0 0
0 1
Sample Output
1
ToT
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1001
分析：参考 BZOJ1027，floyd求最小环，有两个情况要特判，一个是重点，一个室房屋恰好在两点的连线上
O(n*n)暴力枚举所有的点对，对于每个点O(n)检测，如果所有的房子都在一条连线的一侧，则这两个点连线，否则不连，如果这个图中都不存在环，那么输出ToT
下面给出AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 1044266558
typedef struct Point
{
int x, y;
Point operator - ( const Point &b ) const
{
Point c;
c.x = x-b.x; c.y = y-b.y;
return c;
}
double operator * ( const Point &b ) const
{
return x*b.y-y*b.x;
}
}Point;
Point h[], s[];
int n, m, ans, road[][];
bool Jud(Point x, Point y, Point z)
{
if((x.x<z.x && y.x<z.x) || (x.y<z.y && y.y<z.y) || (x.x>z.x && y.x>z.x) || (x.y>z.y && y.y>z.y))
return ;
return ;
}
int main(void)
{
int i, j, k, flag;
while(scanf("%d", &n)!=EOF)
{
memset(road, , sizeof(road));
for(i=;i<=n;i++)
scanf("%d%d", &h[i].x, &h[i].y);
scanf("%d", &m);
for(i=;i<=m;i++)
scanf("%d%d", &s[i].x, &s[i].y);
for(i=;i<=m;i++)
{
for(j=;j<=m;j++)
{
flag = ;
for(k=;k<=n;k++)
{
if((s[i]-s[j])*(s[i]-h[k])< || (s[i]-s[j])*(s[i]-h[k])== && Jud(s[i], s[j], h[k]))
{
flag = ;
break;
}
}
if(flag)
road[i][j] = ;
}
}
ans = inf;
for(k=;k<=m;k++)
{
for(i=;i<=m;i++)
{
if(road[i][k]==inf)
continue;
for(j=;j<=m;j++)
road[i][j] = min(road[i][j], road[i][k]+road[k][j]);
}
}
for(i=;i<=m;i++)
ans = min(ans, road[i][i]);
if(ans>m)
printf("ToT\n");
else
printf("%d\n", m-ans);
}
return ;
}
度度熊的王国战略
Accepts: 173
Submissions: 3298
Time Limit: 40000/20000 MS (Java/Others)
Memory Limit: 32768/132768 K (Java/Others)
Problem Description
度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。
哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。
所以这一场战争，将会十分艰难。
为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。
第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。
哗啦啦族一共有n个将领，他们一共有m个强关系，摧毁每一个强关系都需要一定的代价。
现在度度熊命令你需要摧毁一些强关系，使得内部的将领，不能通过这些强关系，连成一个完整的连通块，以保证战争的顺利进行。
请问最少应该付出多少的代价。
Input
本题包含若干组测试数据。
第一行两个整数n，m，表示有n个将领，m个关系。
接下来m行，每行三个整数u,v,w。表示u将领和v将领之间存在一个强关系，摧毁这个强关系需要代价w
数据范围：
2<=n<=3000
1<=m<=100000
1<=u,v<=n
1<=w<=1000
Output
对于每组测试数据，输出最小需要的代价。
Sample Input
2 1
1 2 1
3 3
1 2 5
1 2 4
2 3 3
Sample Output
1
3
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1002
分析：歪解(并查集可过；正解似乎是堆优化+SW(最小正割)，啥玩意，不懂！
下面给出AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max(a,b) (a)>(b)?(a):(b);
#define min(a,b) (a)>(b)?(b):(a);
inline ll read()//读入优化
{
ll x=,f=;//f表示符号,x表示首位数字0
char ch=getchar();
while(ch<''||ch>'')//如果ch不是数字
{
if(ch=='-')//如果是符号就改变符号
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')//如果ch是数字,接下来的每位数字
{
x=x*+ch-'';//将数字添加进x内
ch=getchar();
}
return x*f;//返回数值
}
inline void write(ll x)//输出优化
{
if(x<)//判断小于0的情况
{
putchar('-');
x=-x;
}
if(x>)//保存每一位
{
write(x/);
}
putchar(x%+'');//输出
}
inline ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
}
const ll INF=1ll<<;
const ll inf=-1ll<<;
const ll N=;
ll pre[N];
bool t[N];//t 用于标记独立块的根结点
inline ll find(ll x)//查找根节点
{
ll r=x;
while(pre[r]!=r)
r=pre[r];//返回根节点 r
int i=x,j;
while(pre[i]!=r)//路径压缩
{
j=pre[i]; // 在改变上级之前用临时变量 j 记录下他的值
pre[i]=r;//把上级改为根节点
i=j;
}
return r;
}
inline void join(ll x,ll y)//判断x y是否连通，
{
ll fx=find(x),fy=find(y);
if(fx!=fy)
pre[fy]=fx;//如果已经连通，就不用管了 //如果不连通，就把它们所在的连通分支合并起来
}
ll n,m;
ll num[N];
int main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)
{
/*
for(i=1;i<=N;i++)
pre[i]=i;//初始化
for(i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
join(a,b);//判断x y是否连通
}
memset(t,0,sizeof(t));
for(i=1;i<=N;i++)
t[find(i)]=1;//标记根结点
for(ans=0,i=1;i<=N;i++)
if(t[i])
ans++;
printf("%d\n",ans-1);
*/
for(ll i=;i<=n;++i)
{
pre[i]=i;
}
memset(num,false,sizeof(num));
ll cnt=;
for(ll i=;i<m;++i)
{
ll x,y,z;
x=read();
y=read();
z=read();
if(x==y)
continue;
num[y]+=z;
num[x]+=z;
if(find(x)!=find(y))
{
pre[find(x)]=find(y);
++cnt;
}
}
if(cnt!=n-)
{
printf("0\n");
continue;
}
ll ans=num[];
for(ll i=;i<=n;i++)
ans=min(ans,num[i]);
write(ans);
printf("\n");
}
return ;
}
度度熊与邪恶大魔王
Accepts: 2114
Submissions: 13031
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。
度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。
当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。
Input
本题包含若干组测试数据。
第一行两个整数n，m,表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<=n<=100000
1<=m<=1000
1<=a[i]<=1000
0<=b[i]<=10
0<=k[i]<=100000
0<=p[i]<=1000
Output
对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1
Sample Input
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6
Sample Output
6
18
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1003
分析：完全背包嘛，签到题的说，对着完全背包看看就好咯，不会的请移步这里
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
typedef __int64 ll;
#define max(a,b) (a)>(b)?(a):(b);
#define min(a,b) (a)>(b)?(b):(a);
inline ll read()//读入优化
{
ll x=,f=;//f表示符号,x表示首位数字0
char ch=getchar();
while(ch<''||ch>'')//如果ch不是数字
{
if(ch=='-')//如果是符号就改变符号
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')//如果ch是数字,接下来的每位数字
{
x=x*+ch-'';//将数字添加进x内
ch=getchar();
}
return x*f;//返回数值
}
inline void write(ll x)//输出优化
{
if(x<)//判断小于0的情况
{
putchar('-');
x=-x;
}
if(x>)//保存每一位
{
write(x/);
}
putchar(x%+'');//输出
}
inline ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
}
const int N=;
const ll INF=1ll<<;
const ll inf=-1ll<<;
ll w[N],v[N];
ll x[N],y[N];
ll dp[][N];
ll n,m;
int main()
{
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
for(ll i=;i<=n;i++)
w[i]=read(),v[i]=read();
for(ll i=;i<=m;i++)
x[i]=read(),y[i]=read();
for(ll i=;i<=;i++)
{
dp[i][]=;
for(ll j=;j<=;j++)
dp[i][j]=INF;
for(ll j=;j<=m;j++)
{
if(y[j]<=i)
continue;
for(ll k=;k<=;k++)
{
ll q=max(k-y[j]+i,);
dp[i][k]=min(dp[i][k],dp[i][q]+x[j]);
}
}
}
ll ans=;
for(ll i=;i<=n;i++)
{
if(dp[v[i]][w[i]]==INF)
{
ans=-;
break;
}
ans+=dp[v[i]][w[i]];
}
write(ans);
printf("\n");
//cout<<ans<<endl;
//printf("%I64d\n",ans);
}
return ;
}
度度熊的午饭时光
Accepts: 375
Submissions: 5441
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。
百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。
但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)
Input
第一行一个整数T，表示T组数据。 每组测试数据将以如下格式从标准输入读入：
B
N
score_1 cost_1
score_2 cost_2
:
score_N cost_N
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。
第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量
从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。
Output
对于每组数据，输出两行： 第一行输出："Case #i:"。i代表第i组测试数据。 第二行输出菜品的总得分和总花费，以空格分隔。 第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。
Sample Input
2
29
6
9 10
3 4
6 5
7 20
10 9
15 11
0
2
2 23
10 12
Sample Output
Case #1:
34 29
2 3 5 6
Case #2:
0 0
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1004
分析：01背包裸题，要在最大化总得分的情况下最小化序号之和，并输出字典序最小的解，在不打饭的情况下不输出空行，嗯，就是介个样子！
下面给出AC代码：
#include <stdio.h>
#include <string.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max(a,b) (a)>(b)?(a):(b);
#define min(a,b) (a)>(b)?(b):(a);
inline ll read()//读入优化
{
ll x=,f=;//f表示符号,x表示首位数字0
char ch=getchar();
while(ch<''||ch>'')//如果ch不是数字
{
if(ch=='-')//如果是符号就改变符号
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')//如果ch是数字,接下来的每位数字
{
x=x*+ch-'';//将数字添加进x内
ch=getchar();
}
return x*f;//返回数值
}
inline void write(ll x)//输出优化
{
if(x<)//判断小于0的情况
{
putchar('-');
x=-x;
}
if(x>)//保存每一位
{
write(x/);
}
putchar(x%+'');//输出
}
inline ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
}
const ll INF=1ll<<;
const ll inf=-1ll<<;
const ll N=;
ll w[N],v[N];
ll u[N];
ll dp[N][N];
bool vis[N][N];
//-------------------------------------------
inline ll solve(ll x,ll y)
{
ll pp=dp[x][];
ll qq=dp[y][];
for(ll p=,q=;p<=pp&&q<=qq;++p,++q)
{
if(dp[pp][p]!=dp[qq][q])
return dp[pp][p]-dp[qq][q];
}
return ;
}
//-------------------------------------------
ll T,n,m;
int main()
{
while(scanf("%lld",&T)!=EOF)
{
//T=read();
for(ll i=;i<=T;++i)
{
m=read();
n=read();
memset(u,false,sizeof(u));
memset(vis,false,sizeof(vis));
memset(dp,false,sizeof(dp));
memset(v,false,sizeof(v));
memset(w,false,sizeof(w));
for(ll j=;j<=n;++j)
{
v[j]=read();
w[j]=read();
}
printf("Case #%lld:\n",i);
for(ll j=;j<=n;++j)
{
for(ll k=m;k>=w[j];--k)
{
//ll a=u[k];
//u[k]=max(u[k],u[k-w[j]]+v[j]);
//if(a!=u[k])
//vis[j][k]=1;
if(u[k]<u[k-w[j]]+v[j])
{
u[k]=u[k-w[j]]+v[j];
vis[j][k]=true;
}
}
}
//
ll maxn=;
for(ll j=;j<=m;++j)
maxn=max(maxn,u[j]);
//
ll sum=INF;
ll x=,num=;
for(ll j=m;j>=;--j)
{
if(u[j]==maxn)
{
ll sumsum=;
ll pre=;
ll xx=n,yy=j;
while(xx>=&&yy>=)
{
if(vis[xx][yy])
{
dp[x][pre++]=xx;
//pre++;
sumsum+=xx;
yy-=w[xx];
}
xx--;
}
dp[x][]=pre-;
sort(dp[x]+,dp[x]++dp[x][]);
if(sum>sumsum)
{
sum=sumsum;
num=x;
}
else if(sum==sumsum&&solve(x,num)<)
{
sum=sumsum;
num=x;
}
x++;
}
}
///
ll val=,cost=;
ll top=dp[num][];
sort(dp[num]+,dp[num]++dp[num][]);
for(ll a=;a<=top;++a)
{
val+=v[dp[num][a]];
cost+=w[dp[num][a]];
}
//printf("Case #%lld:\n",i);
printf("%lld %lld\n",val,cost);
for(ll a=;a<top;++a)
printf("%lld ",dp[num][a]);
if(top>=)
printf("%lld\n",dp[num][top]);
}
}
return ;
}
寻找母串
Accepts: 82
Submissions: 676
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
对于一个串S，当它同时满足如下条件时，它就是一个01偏串： 1、只由0和1两种符组成； 2、在S的每一个前缀中，0的个数不超过1的个数； 3、S中0的个数和1的个数相等。
现在给定01偏串S，请计算一下S在所有长度为n的01偏串中作为子串出现的次数的总和。 由于结果比较大，结果对1e9+7取余后输出。
样例解释： 在第二个样例中，长度为4的偏串共两个1010，1100。10在1010中出现了两次，在1100中出现了1次。所以答案是3。
Input
第一行给出一个整数T(1<=T<=40),表示测试数据的数目。 每一组测试包含一个整数n和字符串S，中间用空格分开。(1<=|S|<=100000，1<=n<=1000000000)
输入保证S是一个01偏串。
Output
对于每一组数据，输出一个整数占一行，表示答案。
Sample Input
2
2 10
4 10
Sample Output
1
3
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1005
分析：
这题看起来束手无策，但其实你可以先写个暴力观察小数据，这个时候你就会发现其实这题比你想象的要简单的多
（比如你会发现其实答案之和字符串的长度|S|有关，和字符串的内容是无关的）
没错！这题有规律，答案就是
但是别高兴的太早，这个时候你又会发现其实这题比你想象的要难得多
因为这题的n范围巨大（约10亿）而求10亿的组合数是做不到的
所有先考虑化简公式看看，令x = (n-|S|)/2+1有
其中F[x]是第x项卡特兰数
通项公式：F[n] = C(2n, n)/(n+1) = C(2n, n)-C(2n, n-1)
递推公式：F[n+1] = 2*(2*n+1)/(n+2)*F[n]
F[n] = F[0]*F[n-1]+F[1]*F[n-2]+…+F[n-1]*F[0]
而卡特兰数有O(n)的递推公式
这样的话理论上可以O(n)求出所有的答案，可还是不行。。。
复杂度已经不能再优化了。。所以只能考虑打表
可是你又开不了10亿的数组，但是这题也没有说要O(1)询问呀
没错！分块打表
你只需要后台O(n)暴力出第100000个卡特兰数，第200000个卡特兰数……第500000000个卡特兰数就好了
也就是开个5000+的数组s[]，其中s[i]是第100000*i个卡特兰数
然后对于每组询问(n, |S|)，先计算x=(n-|S|)/2+1，然后再找到x所在的那一块（比x小离x最近的100000的倍数），
之后暴力转移就好，最多转移100000次
因为有除法所以要乘法逆元，总体复杂度O(100000log(n))
还有注意n为奇数的时候答案一定为0，因为母串要保证0和1的数量相等，所以不存在长度为奇数的母串
除此之外，n<|S|答案也为0
接下来只以10101010101010为例
模式串： 字串： 匹配条件：
10 10 10 1 total 1
1010 10 1010 2
1100 1 total 3
101010 10 101010 3
101100 2
110100 2
110010 2
111000 1 total 10
10101010 10 10101010 4
10101100 3
10110100 3
11010100 3
10110010 3
11001010 3
11010010 3
11011000 2
11001100 2
10111000 2
11101000 2
11100100 2
11100010 2
11110000 1 total 35 即组合数C（n*2-1，n）n=（n-strlen（s））/2+1；
=f[n]*(n+1)/2;
f[n]=2*(2*n-1)*f[n-1]/(i+1);
下面给出AC打表代码：(打了一天的表)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=;
#define max(a,b) (a)>(b)?(a):(b);
#define min(a,b) (a)>(b)?(b):(a);
inline ll read()//读入优化
{
ll x=,f=;//f表示符号,x表示首位数字0
char ch=getchar();
while(ch<''||ch>'')//如果ch不是数字
{
if(ch=='-')//如果是符号就改变符号
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')//如果ch是数字,接下来的每位数字
{
x=x*+ch-'';//将数字添加进x内
ch=getchar();
}
return x*f;//返回数值
}
inline void write(ll x)//输出优化
{
if(x<)//判断小于0的情况
{
putchar('-');
x=-x;
}
if(x>)//保存每一位
{
write(x/);
}
putchar(x%+'');//输出
}
ll pre[N];
bool t[N];//t 用于标记独立块的根结点
inline ll find(ll x)//查找根节点
{
ll r=x;
while(pre[r]!=r)
r=pre[r];//返回根节点 r
int i=x,j;
while(pre[i]!=r)//路径压缩
{
j=pre[i]; // 在改变上级之前用临时变量 j 记录下他的值
pre[i]=r;//把上级改为根节点
i=j;
}
return r;
}
inline void join(ll x,ll y)//判断x y是否连通，
{
ll fx=find(x),fy=find(y);
if(fx!=fy)
pre[fy]=fx;//如果已经连通，就不用管了 //如果不连通，就把它们所在的连通分支合并起来
}
const ll mod=;
inline ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
}
inline ll qpow(ll x,ll p)
{
ll ret=;
for(;p;p>>=,x=x*x%mod)
{
if(p&)
ret=ret*x%mod;
}
return ret;
}
const ll INF=1ll<<;
const ll inf=-1ll<<;
char str[N];
ll s[N]=
{
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
};
ll T,n;
int main()
{
ios::sync_with_stdio(false);
T=read();
while(T--)
{
scanf("%d%s",&n,&str);
ll len=strlen(str);
if(len>n||n&)
{
printf("0\n");
continue;
}
ll pp=(n-len)/+;
ll x=pp/;
ll ans=s[x];
for(ll i=x*+;i<=pp;++i)
ans=(ans**(i*-)%mod*qpow(i+,mod-)%mod)%mod;
ans=(ans*(pp+)%mod*qpow(,mod-)%mod)%mod;
write(ans);
printf("\n");
}
return ;
}