結果

問題 No.1702 count good string
ユーザー publfl
提出日時 2021-10-08 22:24:36
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

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