結果

問題 No.1702 count good string
ユーザー publflpublfl
提出日時 2021-10-08 22:24:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 1,946 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 76,784 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-30 10:51:17
合計ジャッジ時間 5,238 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,384 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 125 ms
4,376 KB
testcase_14 AC 125 ms
4,376 KB
testcase_15 AC 124 ms
4,376 KB
testcase_16 AC 125 ms
4,380 KB
testcase_17 AC 124 ms
4,380 KB
testcase_18 AC 125 ms
4,380 KB
testcase_19 AC 126 ms
4,376 KB
testcase_20 AC 125 ms
4,380 KB
testcase_21 AC 125 ms
4,380 KB
testcase_22 AC 124 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 3 ms
4,376 KB
testcase_25 AC 3 ms
4,384 KB
testcase_26 AC 3 ms
4,380 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 3 ms
4,380 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 3 ms
4,376 KB
testcase_32 AC 2 ms
4,380 KB
testcase_33 AC 101 ms
4,380 KB
testcase_34 AC 101 ms
4,380 KB
testcase_35 AC 102 ms
4,380 KB
testcase_36 AC 101 ms
4,380 KB
testcase_37 AC 101 ms
4,376 KB
testcase_38 AC 101 ms
4,380 KB
testcase_39 AC 102 ms
4,376 KB
testcase_40 AC 100 ms
4,380 KB
testcase_41 AC 100 ms
4,376 KB
testcase_42 AC 101 ms
4,376 KB
testcase_43 AC 22 ms
4,376 KB
testcase_44 AC 23 ms
4,376 KB
testcase_45 AC 2 ms
4,376 KB
testcase_46 AC 2 ms
4,376 KB
testcase_47 AC 1 ms
4,376 KB
testcase_48 AC 1 ms
4,380 KB
testcase_49 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <stdio.h>
#include <algorithm>
#include <map>
#include <vector>
#define MOD 1000000007
#define MOD1 998244353
#define MOD2 1000000007
#define MUL 99999971

char x[110];
std::vector< std::pair<long long int, long long int> > index,ans;
std::map< std::pair<long long int, long long int> , int > hash;
void hashF()
{
	long long int sum1 = 0, sum2 = 0;
	for(int i=1;i<=9;i++)
	{
		sum1 *= MUL, sum2 *= MUL;
		sum1 += x[i], sum2 += x[i];
		sum1 %= MOD1, sum2 %= MOD2;
		index.push_back(std::make_pair(sum1,sum2));
	}
	ans.push_back(std::make_pair(sum1,sum2));
}

char y[100010];
std::map< std::pair<long long int, long long int> , long long int> count,count2;
int main()
{
	x[1] = 'y', x[2] = 'u', x[3] = 'k', x[4] = 'i', x[5] = 'c', x[6] = 'o', x[7] = 'd', x[8] = 'e', x[9] = 'r';
	index.push_back(std::make_pair(0,0));
	hashF();
	
	for(int i=1;i<=9;i++)
	{
		char temp = x[i];
		x[i] = '?';
		hashF();
		x[i] = temp;
	}
	
	std::sort(index.begin(),index.end());
	for(int i=0;i<index.size();i++) hash[index[i]] = i+1;
	int n = index.size();
	count[std::make_pair(0,0)] = 1;
	
	int a;
	scanf("%d",&a);
	scanf("%s",y+1);
	for(int i=1;i<=a;i++)
	{
		count2.clear();
		for(std::map< std::pair<long long int, long long int> ,long long int> ::iterator it = count.begin();it!=count.end();it++)
		{
			long long int sum1 = (it->first).first;
			long long int sum2 = (it->first).second;
			sum1 *= MUL, sum2 *= MUL, sum1 += y[i], sum2 += y[i], sum1 %= MOD1, sum2 %= MOD2;
			if(hash.find(std::make_pair(sum1,sum2))!=hash.end())
			{
				count2[std::make_pair(sum1,sum2)] += (it->second), count2[std::make_pair(sum1,sum2)] %= MOD;
			}
		}
		for(std::map< std::pair<long long int, long long int> ,long long int> ::iterator it = count2.begin();it!=count2.end();it++)
		{
			count[it->first] += (it->second), count[it->first] %= MOD;
		}
	}
	
	long long int sum = 0;
	for(int i=0;i<ans.size();i++) sum += count[ans[i]], sum %= MOD;
	printf("%lld",sum);
}
0