【问题描述】

据说鼎纹的 种制造 式是 铜模印出来的，这是我国古代劳动 智慧

的结晶。铜模印过的地 ，会留下深深的印记，经过时间的炼化，洗

练成历史的遗存。

聪明的古代劳动人民拥有一个 a 行 b 列的铜模，每个位置要么是 （代表

这个点是平的），要么是 （代表这个点是凸起的）。他们想造 个 n 行 m 列

的鼎 ，其中每个位置也都是  或 ，表示经过若干 次印后，每个位置的结果。

有一些要求。铜模是不能旋转和翻转的；在印的过程当中，铜模的凸起不

能出现在鼎面的外面（平的部分是可以出现在外面的），鼎面上的同一个位置

不能被多个凸起印下（在任意两次印时，鼎面上不存在一个点，使得这两次都

有铜模上为  的点覆盖它）。

请你判断这个鼎面能不能被印出来。

 【输入格式】

输入文件件名为 grain.in。

本题多测。

第一行，一个整数 T ，表示测试

点数量。接下来 T 个测试点，每

个测试点中：

第一行包含  个整数 n,m,a,b。

接下来 n 行 ，每行 m 个字符，描述鼎面 。“”表示

平，“”表示凸起。接下来 a 行，每行 b 个字符，

描述铜模。“”表示平，“”表示凸起。

【输出格式】

输出 件名为 grain.out。

共有 T 行 ，对于每个测试点，输出 “YES”（能）或“NO”（不能）。

 【样例】

grain.in

grain.out

YES

NO

 【数据规模与约定】

对于 % 的数据，n,m,a, b <= 。

对于 % 的数据， <= T <=; <=n,m, a, b <= 。

【问题描述】

据说鼎纹的 种制造 式是 铜模印出来的，这是我国古代劳动 智慧

的结晶。铜模印过的地 ，会留下深深的印记，经过时间的炼化，洗

练成历史的遗存。

聪明的古代劳动人民拥有一个 a 行 b 列的铜模，每个位置要么是 （代表

这个点是平的），要么是 （代表这个点是凸起的）。他们想造 个 n 行 m 列

的鼎 ，其中每个位置也都是  或 ，表示经过若干 次印后，每个位置的结果。

有一些要求。铜模是不能旋转和翻转的；在印的过程当中，铜模的凸起不

能出现在鼎面的外面（平的部分是可以出现在外面的），鼎面上的同一个位置

不能被多个凸起印下（在任意两次印时，鼎面上不存在一个点，使得这两次都

有铜模上为  的点覆盖它）。

请你判断这个鼎面能不能被印出来。

 【输入格式】

输入文件件名为 grain.in。

本题多测。

第一行，一个整数 T ，表示测试

点数量。接下来 T 个测试点，每

个测试点中：

第一行包含  个整数 n,m,a,b。

接下来 n 行 ，每行 m 个字符，描述鼎面 。“”表示

平，“”表示凸起。接下来 a 行，每行 b 个字符，

描述铜模。“”表示平，“”表示凸起。

【输出格式】

输出 件名为 grain.out。

共有 T 行 ，对于每个测试点，输出 “YES”（能）或“NO”（不能）。

 【样例】

grain.in

grain.out

YES

NO

 【数据规模与约定】

对于 % 的数据，n,m,a, b <= 。

对于 % 的数据， <= T <=; <=n,m, a, b <= 。

题目

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #define maxn 1010

 using namespace std;

 int T,n,m,a,b,cnt1,cnt2,mp[maxn][maxn],x[maxn*maxn],y[maxn*maxn],X[maxn*maxn],Y[maxn*maxn];

 char ch[maxn];

 void init()

 {

     for(int i=;i<=n;++i)

         for(int j=;j<=m;++j)

             mp[i][j]=;

     for(int i=;i<=cnt1;++i) x[i]=y[i]=;

     for(int i=;i<=cnt2;++i) X[i]=Y[i]=;

     cnt1=cnt2=;

 }

 bool check(int xx,int yy)

 {

     mp[xx][yy]=;

     for(int i=;i<=cnt2;++i){

          int XX=xx+X[i],YY=yy+Y[i];

          if(XX<||XX>n||YY<||YY>m||!mp[XX][YY]) return false;

          mp[XX][YY]=;

     }

     return true;

 }

 void solve()

 {

     init();

     scanf("%d%d%d%d",&n,&m,&a,&b);

     for(int i=;i<=n;++i){

         scanf("%s",ch+);

         for(int j=;j<=m;++j){

             if(ch[j]-''){

                 x[++cnt1]=i;

                 y[cnt1]=j;

                 mp[i][j]=;

             }

         }

     }

         //记录鼎的1

     for(int i=;i<=a;++i){

         scanf("%s",ch+);

         for(int j=;j<=b;++j){

             if(ch[j]-''){

                 X[++cnt2]=i;

                 Y[cnt2]=j;

             }

         }//记录模的1

     }

     for(int i=;i<=cnt2;++i){

         X[i]-=X[];

         Y[i]-=Y[];

     }//模版的几个1到第一个1的距离

     for(int i=;i<=cnt1;++i)

         if(mp[x[i]][y[i]])

             if(!check(x[i],y[i])){

                 puts("NO");

                 return;

             }

     puts("YES");

 }

 int main()

 {

     //freopen("grain.in","r",stdin);

     //freopen("grain.out","w",stdout);

     scanf("%d",&T);

     while(T--) solve();

     return ;

 } 

 年 里奥迪奥带领的十星巴西对战莱昂纳多带领的阿根廷的世界杯决赛马

上开始了！前来在巨型球场观看比赛的观众数不甚数，但是由于突如其来的系统

原因，大家不能网上购票，只能到售票窗口，排成长龙买票. 按售票处规定，每一个限购一张门票，且每一张门票  美元。 在排成长龙的球

迷中有 n 个人手持  美元，另外有 n 个人手持  美元。假设售票处开始的时

候没有零钱，试问这 2n 个球迷有多少种排队方式使得售票处不会出现找不出钱

的尴尬局面，导致拖延球迷看球时间。

【输入与输出说明】

输入两行，第一行一个正整数 T，表示数据个数。

第二行有 T 个正整数，n1,n2,....nT. 输出 T 行，每一行为被 ^+ 模过的结果。

【样例输入1】 

【样例输出1】

【样例输入2】 

【样例输出2】

【样例说明】

例如当 n= 时，用 A 表示手持面值  美元的球迷，用 B 表示手持面值为  美

元的球迷，则最多可得到以下两组不同的排队方式使得售票处不会出现找不出钱

的情况。

售票处 A A B B

售票处 A B A B

【数据范围】

对于 % n <= , T <=

对于 % n <= , T <=

对于 % n <= , T <=

对于其中 %  < n <= ^, T <=

对于其中 % ^ < n <= *^, T = 

题目

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int mod=1e9+;

 int T,n;

 int ksm(int x,int y)

 {

     int ret=,b=y;

     while(b)

     {

         if(b&) ret=1ll*ret*x%mod;

         x=1ll*x*x%mod;

         b>>=;

     }

     return ret;

 }

 int solve()

 {

     int ret1=,ret2=;

     for(int i=;i<=n;++i){

         ret1=1ll*ret1*(n+i)%mod;

         ret2=1ll*ret2*i%mod;

     }

     return 1ll*ret1*ksm(ret2,mod-)%mod;

 }

 int main()

 {

     //freopen("football.in","r",stdin);

     //freopen("football.out","w",stdout);

     scanf("%d",&T);

     while(T--){

         scanf("%d",&n);

         printf("%d\n",solve());

     }

     return ;

 }