# WustOJ 1575 Gingers and Mints(快速幂 + dfs )

## 1575: Gingers and Mints

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 24  Accepted: 13
[Submit][Status][Web Board]

## Description

fcbruce
owns a farmland, the farmland has n * m grids. Some of the grids are
stones, rich soil is the rest. fcbruce wanna plant gingers and mints on
his farmland, and each plant could occupy area as large as possible. If
two grids share the same edge, they can be connected to the same area.
fcbruce is an odd boy, he wanna plant gingers, which odd numbers of
areas are gingers, and the rest area, mints. Now he want to know the
number of the ways he could plant.

## Input

The first line of input is an integer T (T < 100), means there are T test cases.

For each test case, the first line has two integers n, m (0 < n, m < 100).

For next n lines, each line has m characters, ‘N‘ for stone, ‘Y‘ for rich soil that is excellent for planting.

## Output

For each test case, print the answer mod 1000000007 in one line.

```2
3 3
YNY
YNN
NYY
3 3
YYY
YYY
YYY```

```4
1```

## HINT

For the
first test case, there are 3 areas for planting. We marked them as A, B
and C. fcbruce can plant gingers on A, B, C or ABC. So there are 4 ways
to plant gingers and mints.

## Author

fcbruce

1.先用DFS求出联通块个数。

2.再根据数学知识 C{n,1} + C{n,3} + C{n,5} + ... = 2^(n-1) 用快速幂求出。

```#include<cstdio>
#include<cstring>
using namespace std;

#define maxn 200
char pic[maxn][maxn];
int vis[maxn][maxn];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int n,m;

void dfs(int x, int y)
{
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(!vis[nx][ny] && pic[nx][ny] == ‘Y‘ && nx >= 0 && nx < n && ny >= 0 && ny < m)
{
vis[nx][ny] = 1;
dfs(nx,ny);
}
}
}
int pow_mod(int a,int n,int m)
{

if(n==0)
return  1;
int x=pow_mod(a,n/2,m);
long long ans=(long long)x*x%m;
if(n%2==1)
ans=ans*a%m;
return (int )ans;
}

int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++)
scanf("%s", pic[i]);
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(!vis[i][j] && pic[i][j] == ‘Y‘)
{
vis[i][j] = 1;
cnt++;
dfs(i,j);
}
}
printf("%d\n",pow_mod(2,cnt-1,1000000007));
}
return 0;
}```

## hdu 1575 try a 矩阵快速幂

#include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<queue> #include<stack> #include<algorithm> #include<iostream> using namespace std; #define ll long long int const int m=9973; ll

## 矩阵快速幂——将运算推广到矩阵上HDU 1575

/* 本题的思路比较简单,就是将递推公式写出来,然后表达成为一个矩阵的形式 最后通过计算就可以得到一个符合题目要求的矩阵, 然后就是将矩阵上面所有的对角线元素相加 得到的结果即为所求的目标 */ #include<cstdio>  #include<cstring>  using namespace std;  const int maxn = 15;  #define mod 9973  int res[maxn][maxn];  int n;  void mul(int a[]

## HDU 1575 Tr A（矩阵快速幂）

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5537    Accepted Submission(s): 4161 Problem Description A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input 数据的第一行是一个T,表示有T组数据.每组数据的第一行有n(2 <=

## hdu 1575 求一个矩阵的k次幂 再求迹 （矩阵快速幂模板题）

Problem DescriptionA为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input数据的第一行是一个T,表示有T组数据.每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据.接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容. Output对应每组数据,输出Tr(A^k)%9973. Sample Input22 21 00 13 999999991 2 34

## hdoj 1575 Tr A 【矩阵快速幂】

Tr A Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3020    Accepted Submission(s): 2251 Problem Description A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input 数据的第一行是一个T,表示有T组数据. 每组数据的第一行有