#705672 (C++14) No.1702 count good string

提出ソース

結果

問題	No.1702 count good string
ユーザー	publfl
提出日時	2021-10-08 22:24:36
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	124 ms / 2,000 ms
コード長	1,946 bytes
コンパイル時間	1,097 ms
コンパイル使用メモリ	77,356 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-23 04:57:15
合計ジャッジ時間	4,685 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	122 ms 5,376 KB
testcase_14	AC	122 ms 5,376 KB
testcase_15	AC	120 ms 5,376 KB
testcase_16	AC	122 ms 5,376 KB
testcase_17	AC	122 ms 5,376 KB
testcase_18	AC	122 ms 5,376 KB
testcase_19	AC	124 ms 5,376 KB
testcase_20	AC	123 ms 5,376 KB
testcase_21	AC	121 ms 5,376 KB
testcase_22	AC	122 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	3 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	3 ms 5,376 KB
testcase_29	AC	3 ms 5,376 KB
testcase_30	AC	3 ms 5,376 KB
testcase_31	AC	3 ms 5,376 KB
testcase_32	AC	3 ms 5,376 KB
testcase_33	AC	97 ms 5,376 KB
testcase_34	AC	97 ms 5,376 KB
testcase_35	AC	95 ms 5,376 KB
testcase_36	AC	96 ms 5,376 KB
testcase_37	AC	97 ms 5,376 KB
testcase_38	AC	95 ms 5,376 KB
testcase_39	AC	98 ms 5,376 KB
testcase_40	AC	98 ms 5,376 KB
testcase_41	AC	96 ms 5,376 KB
testcase_42	AC	96 ms 5,376 KB
testcase_43	AC	22 ms 5,376 KB
testcase_44	AC	23 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB
testcase_47	AC	2 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
}

yukicoder

結果

テストケース

ソースコード