度度熊保护村庄

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

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

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

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组数据。每组测试数据将以如下格式从标准输入读入：

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

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

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 ;

 }

巴特西

2017"百度之星"程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集)，1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】

度度熊保护村庄

度度熊的王国战略

度度熊与邪恶大魔王

度度熊的午饭时光

寻找母串

最新文章

热门文章