链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
小Why拿到了一个密码长度为 mmm 的密码锁，这个密码锁可输入内容无限，并只对最后输入的 mmm 位字符进行检测，检测正确时密码锁会解锁一次，同时清空包含检测正确字符串在内的之前的所有字符。
小Why输入了一个长度为 nnn 的字符串 sss 后，密码锁一共解锁了 kkk 次，请你告诉他有多少种密码是可能正确的。
输入描述:
第一行包含三个整数 n,m,k (1≤m∗k≤n≤106)n,m,k \ (1 \leq m*k \leq n \leq 10^6)n,m,k (1≤m∗k≤n≤106)，表示字符串 sss 的长度，密码长度和解锁次数。
第二行包含一个长度为 n \ n \ n 的字符串 sss，保证字符串 sss 中只含有 0∼90\sim90∼9 的数字。
分析：
字符串哈希unsigned long long类型
#include<bits/stdc++.h>
typedef long long ll;
#define ull unsigned long long
using namespace std;
const ll N=1e6+3;
const ull mod=1313;
ull p[N],h[N];
ull get(ll l,ll r)
{
return h[r]-h[l-1]*p[r-l+1];
}
void solve()
{
memset(p,0,sizeof p);
memset(h,0,sizeof h);
ll n,m,k;
cin>>n>>m>>k;
map<ull,ull> hash,la;
string s;
cin>>s;
s=" "+s;
p[0]=1;
for(ll i=1;i<=n;i++)
{
p[i]=p[i-1]*mod;
h[i]=mod*h[i-1]+s[i];
}
for(ll i=1;i+m-1<=n;i++)
{
ull res=get(i,i+m-1);
if(la[res]&&la[res]+m-1>=i)continue;
la[res]=i;
hash[res]++;
}
ull sums=0;
for(auto [uu,vv]:hash)
{
if(vv==k)sums++;
}
cout<<sums<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t=1;
while(t--)
solve();
return 0;
}