結果

問題 No.1702 count good string
ユーザー publflpublfl
提出日時 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0