Submission #7981365


Source Code Expand

Copy
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
}
// ここから編集しろ
char in[310][310];
long long dp[2][310][310];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",in[i]);
	dp[0][0][0]=1;
	init_C(1100);
	for(int i=0;i<a+b-1;i++){
		int t=i%2;
		for(int j=0;j<a;j++)for(int k=0;k<a;k++)dp[!t][j][k]=0;
		for(int j=0;j<a;j++){
			if(i<j||i-j>=b)continue;
			for(int k=0;k<a;k++){
				if(i<k||i-k>=b)continue;

				long long D1=1;
				if(i-j+1<b)D1=d2;
				long long D2=1;
				// if(i-k+1<b)D2=d2;
				long long R1=1;
				if(j+1<a)R1=d2;
				long long R2=1;
				// if(k+1<a)R2=d2;
				
				if(j+1<a&&k+1<a&&in[j+1][i-j]==in[k+1][i-k]){
					dp[!t][j+1][k+1]=(dp[!t][j+1][k+1]+dp[t][j][k]*D1%mod*D2)%mod;
				}
				if(j+1<a&&i-k+1<b&&in[j+1][i-j]==in[k][i-k+1]){
					dp[!t][j+1][k]=(dp[!t][j+1][k]+dp[t][j][k]*D1%mod*R2)%mod;
				}
				if(i-j+1<b&&k+1<a&&in[j][i-j+1]==in[k+1][i-k]){
					dp[!t][j][k+1]=(dp[!t][j][k+1]+dp[t][j][k]*R1%mod*D2)%mod;
				}
				if(i-j+1<b&&i-k+1<b&&in[j][i-j+1]==in[k][i-k+1]){
					dp[!t][j][k]=(dp[!t][j][k]+dp[t][j][k]*R1%mod*R2)%mod;
				}
				
			}
		}
	}
	long long ret=dp[(a+b)%2][a-1][a-1];
	for(int i=0;i<a+b;i++)ret=(ret+ret)%mod;
	printf("%lld\n",ret);
}

Submission Info

Submission Time
Task A - Code
User tozangezan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3006 Byte
Status AC
Exec Time 351 ms
Memory 5760 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:80:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int a,b;scanf("%d%d",&a,&b);
                             ^
./Main.cpp:81:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<a;i++)scanf("%s",in[i]);
                                       ^

Judge Result

Set Name Set 01 Set 02 Set 03 Set 04 Set 05 Set 06 Set 07 Set 08 Set 09 Set 10
Score / Max Score 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10 10 / 10
Status
AC × 3
AC × 4
AC × 3
AC × 4
AC × 3
AC × 4
AC × 4
AC × 3
AC × 3
AC × 3
Set Name Test Cases
Set 01 01-01, 01-02, 01-03
Set 02 02-01, 02-02, 02-03, 02-04
Set 03 03-01, 03-02, 03-03
Set 04 04-01, 04-02, 04-03, 04-04
Set 05 05-01, 05-02, 05-03
Set 06 06-01, 06-02, 06-03, 06-04
Set 07 07-01, 07-02, 07-03, 07-04
Set 08 08-01, 08-02, 08-03
Set 09 09-01, 09-02, 09-03
Set 10 10-01, 10-02, 10-03
Case Name Status Exec Time Memory
01-01 AC 1 ms 4352 KB
01-02 AC 1 ms 4352 KB
01-03 AC 1 ms 4352 KB
02-01 AC 1 ms 4224 KB
02-02 AC 1 ms 4352 KB
02-03 AC 1 ms 4352 KB
02-04 AC 1 ms 4352 KB
03-01 AC 2 ms 4480 KB
03-02 AC 2 ms 4480 KB
03-03 AC 2 ms 4480 KB
04-01 AC 2 ms 4480 KB
04-02 AC 2 ms 4480 KB
04-03 AC 2 ms 4480 KB
04-04 AC 3 ms 4480 KB
05-01 AC 15 ms 4736 KB
05-02 AC 13 ms 4864 KB
05-03 AC 24 ms 4864 KB
06-01 AC 1 ms 4224 KB
06-02 AC 38 ms 5120 KB
06-03 AC 44 ms 5248 KB
06-04 AC 61 ms 5120 KB
07-01 AC 5 ms 5248 KB
07-02 AC 91 ms 5248 KB
07-03 AC 84 ms 5248 KB
07-04 AC 102 ms 5248 KB
08-01 AC 1 ms 4224 KB
08-02 AC 233 ms 5760 KB
08-03 AC 290 ms 5760 KB
09-01 AC 284 ms 5760 KB
09-02 AC 246 ms 5760 KB
09-03 AC 351 ms 5760 KB
10-01 AC 233 ms 5760 KB
10-02 AC 294 ms 5760 KB
10-03 AC 351 ms 5760 KB