【SinGuLaRiTy-1034】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
度度熊保护村庄
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
解析
首先我们要知道，由于是"包围"村庄，那么用来包围这个村庄的守卫连接的边都不能穿过村庄。如下图所示：在所有满足条件的边中，绿色边的包围方案最佳。
到这时，我们的问题就可以从找最少点变成找最少边——而这一点有非常好办，只要处理出上图这样的样子，给每一个边都赋值为1，求一个最小环就行了。那么问题来了，怎样才能选出满足条件的边呢？显然的是，我们首先需要n^2的枚举两个包围的端点，从而确定一条边，接着才是重点：判断相交。显然，如果对村庄的房子也采用先前的方法m^2枚举，总的时间复杂度是O(n^2*m^2)，肯定超时。这时，我们就要稍稍转换一下：如果一条边没有穿过村庄，那么所有的房子一定在它的一侧呀！于是，我们在判定每一条边时，只用枚举m次，看看这m个点是否都在同一侧就行了，如果不在同一侧，就去掉这条边。经过这个O(n^2*m)的判定过程，我们就可以处理出仅包含可行边的图，接下来跑一次最短路就可以啦。其它的问题嘛：就要看看代码实现了。
好吧，还是提一下关于"判定线段是否相交"的问题，有两个试验：快速排斥实验和跨立实验，通过这两个试验可以在不求交点的情况下快速判断线段是否相交。那么怎么实现呢？网上的博客有很多，自己去查吧！
度度熊的王国战略
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
解析
由题意得，对于本来就不是强连通图的数据，我们直接输出"0"就行了。对于另外的大部分情况，我们很容易发现:只要将边权和最小的点从图中删去就行了。在实现过程中，可以考虑使用并查集(谁说图论题就一定要建一个图)。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdlib> using namespace std; int sum[],ufs[]; int Find(int x)
{
if(ufs[x]==)
return x;
return ufs[x]=Find(ufs[x]);
} int main(void)
{
int n,m,i,x,y,z,cnt,t1,t2;
while(scanf("%d%d",&n,&m)!=EOF)
{
cnt=n-;
memset(ufs,,sizeof(ufs));
memset(sum,,sizeof(sum));
for(i=;i<=m;i++)
{
cin>>x>>y>>z;
if(x==y)
continue;
sum[x]+=z;
sum[y]+=z;
t1=Find(x);
t2=Find(y);
if(t1!=t2)
{
ufs[t1]=t2;
cnt--;
}
}
if(cnt==)
{
sort(sum+,sum+n+);
printf("%d\n",sum[]);
}
else
printf("0\n");
}
return ;
}
度度熊与邪恶大魔王
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
解析
注意到防御值最大才为10，所以肯定是用防御力来遍历。设dp[j][i]为防御力为 i ,打出 j点伤害以上时所需的最少晶石。
对于第u个技能来说，如果p[u]<= i，说明根本打不出伤害，不用管。
反之，伤害则为 dmg=p[u]-i, 这时候 又有两种情况：
如果dmg>=j，说明靠这一个技能就够打出足够伤害了，那么肯定是用消耗晶石最少的那个技能，dp[j][i]=min{k[u]}；
反之，光靠这个技能不足以打出足够的伤害，那么就需要借助前面的dp值来计算，dp[j-dmg][i]代表同在i防御力，打出j-dmg的伤害的最少晶石，因为dp[j-dmg][i]数量的晶石已经可以打出 j-dmg 的伤害了，此时再加上这第u个技能的伤害，就可以打到 j 以上，晶石数则为dp[j-dmg][i]+k[u],与上面一样，因为不知道哪个技能消耗的晶石最少，所以这里也取一个最小值。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio> #define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const int maxn=+;
const int maxm=+; LL a[maxn],b[maxn];
LL k[maxm],p[maxm];
LL dp[maxm][]; LL max(LL a,LL b)
{
return a>b?a:b;
}
LL min(LL a,LL b)
{
return a<b?a:b;
} int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
LL up1=,up2=,hp=;
for(int i=; i<n; i++)
{
scanf("%I64d%I64d",&a[i],&b[i]);
up1=max(up1,b[i]);
hp=max(hp,a[i]);
} for(int i=; i<m; i++)
{
scanf("%I64d%I64d",&k[i],&p[i]);
up2=max(up2,p[i]);
}
if(up1>=up2)
{
printf("-1\n");
continue;
}
mem(dp,);
for(int i=; i<=; i++)
{
for(int j=;j<=hp;j++)
{
dp[j][i]=1e18;
for(int u=;u<m;u++)
{
LL dmg=p[u]-i;
if(dmg<=)
continue;
if(dmg>=j)
{
dp[j][i]=min(dp[j][i],k[u]);
}
else
{
dp[j][i]=min(dp[j][i],dp[j-dmg][i]+k[u]);
}
}
}
}
LL ans=;
for(int i=;i<n;i++)
{
ans+=dp[a[i]][b[i]];
}
printf("%I64d\n",ans); }
return ;
}
度度熊的午饭时光
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
解析
读完题，应该都可以看出这是一道01背包。DP的方程式都是模板，不解释了。这题的所谓的"不同之处"就在于要求求出DP的路径，其实也和简单，对于dp[i][j]的每一个状态，都对应一个vis[i][j]来记录到达这一状态的路径就可以了，在DP过程中边递推，边维护，最后再顺着一个一个printf出来就可以了。
Code
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<iostream> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const ll mod=1e9+; struct meal
{
int score,cost;
}a[]; bool ans[];
int dp[];
bool vis[][]; int main()
{
int T,Case=;
cin>>T;
while(T--)
{
int b,n;
cin>>b>>n;
for(int i=;i<=n;i++)
cin>>a[i].score>>a[i].cost;
memset(dp,,sizeof(dp));
memset(vis,false,sizeof(vis));
memset(ans,,sizeof(ans));
for(int i=;i<=n;i++)
{
for(int j=b;j>=;j--)
{
if(j>=a[i].cost)
{
if(dp[j]<dp[j-a[i].cost]+a[i].score)
{
dp[j]=dp[j-a[i].cost]+a[i].score;
vis[i][j]=true;
}
else
vis[i][j]=false;
}
}
}
int p=b,cnt=;
for(int i=n;i>=;i--)
{
if(vis[i][p])
{
ans[i]=true;
p-=a[i].cost;
cnt++;
}
}
int ANS=;
for(int i=;i<=n;i++)
{
if(ans[i])
ANS+=a[i].cost;
}
printf("Case #%d:\n",Case++);
printf("%d %d\n",dp[b],ANS);;
for(int i=;i<=n;i++)
{
if(ans[i])
{
cout<<i;
if(--cnt)
cout<<" ";
else
cout<<endl;
}
}
}
return ;
}
寻找母串
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
解析
首先，写一个暴力，观察观察——这一看不得了，似乎有规律！我们发现，固定好n，只要字符串的长度固定，无论字符串的内容是什么，答案都是一样的。接着再继续深入地研究一下，我们竟然发现答案就是。
接下来，我们将它化简，可以得到：原式=F((n-|S|)/2+1)*((n-|S|)/2+1+1)/2。其中的F(n)指的就是卡特兰数列的第n项。我们又会欣喜地发现：卡特兰数列有O(n)的递推公式！
不过我们高兴的太早了：这里的n可是很大的，这么大的n，一个数组也开不下呀。于是我们就要用到分块的思想：n不是有很大吗，我们把1~(n-|S|)/2+1)的大区间划分成许多个小区间，后台暴力打表搞出第100000,200000,300000......500000000个卡特兰数，接着判断输入的 (n-|S|)/2+1)在哪一个区间里，再直接在这个区间里面递推，这样单次的递推的时间复杂度就变为了O(100000)。注意，由于在计算答案时数据可能会比较大，需要用到乘法逆元，不过这很好办，稍稍观察就会发现，所求的逆元的值恒为500000004，直接代入就行了。
另外大家还要注意两点: 1>对于n<|S|这一类情况，要提前特判输"0"；2>对于n%2!=0的情况，也要特判输"0"，因为01串要满足0和1的个数相同，那么长度一定为偶数。表示本人为此WA掉了20多次......qwq。
Code
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdlib> #define ll long long
#define mod 1000000007
#define inverse_element 500000004 using namespace std; int c[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}; ll Pow(ll a,ll b)
{
ll sum=;
while(b)
{
if(b%)
sum=sum*a%mod;
a=a*a%mod;
b/=;
}
return sum;
} int n;
char S[]; int main()
{
int T;
cin>>T;
for(int t=;t<=T;t++)
{
memset(S,,sizeof(S));
cin>>n;
cin>>S;
int len=strlen(S);
if(n<len||n%!=)
{
cout<<""<<endl;
continue;
}
ll tool=(n-len)/+;
int i;
for(i=;i<=;i++)
{
if(i*>tool)
{
break;
}
}
ll now=c[i-];
for(ll j=(i-)*+;j<=tool;j++)
{
now=*(*j-)%mod*now%mod*Pow(j+,mod-)%mod;
}
ll ans=now%mod*(((tool+)%mod*inverse_element)%mod)%mod;
cout<<ans<<endl;
}
return ;
}
Time: 2017-08-06