2022-1-7

本文主要是介绍2022-1-7，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D. Period

题意：给你一个字符串，q次查询，每次查询会将字符串中的一个字符修改为#，求在新串中可以选出几种长度不同的前后缀，使得前后缀相同

分析：对于长度为n的串，#在pos位置时，只需对长度小于等于min(pos-1,n-pos)的前后缀查询即可 
q在1e6 故要先预处理主串看看有哪些长度的前后缀是相通的 再O(1)查询 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
*/
const int N=1e6+10;
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
int ans[N];
int n,P=131;
char s[N];

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r){
    return h[r]-h[l-1]*p[r-l+1];
}

void gethash(){
    p[0]=1;
    for (int i=1; i<=n; i++ ){
       h[i]=h[i-1]*P+s[i]-'a'+1;
       p[i]=p[i-1]*P;
  }
}

int main()
{
    scanf("%s",s+1);
	n=strlen(s+1);
	gethash();
	for(int i=1;i<=n/2;i++)
		if(get(1,i)==get(n-i+1,n))
			ans[i]=ans[i-1]+1;//前缀长度为i时能取到的最大方案数
		else
            ans[i]=ans[i-1];

	int m;
	cin>>m;
	while(m--){
		int pos;
		scanf("%d",&pos);
		pos=min(pos-1,n-pos);
		printf("%d\n",ans[pos]);
	}

    return 0;
}

G. Desserts

#include <iostream>
#include <bits/stdc++.h>
typedef long long  ll;
using namespace std;
/*
对1e5 数据预处理一下； 将i的阶乘存入fac[]; fac[i]逆元存入inv_[] 
输入时 
统计某类最大糖果， 当所分小组小于该最大者 直接输出0;
按糖果数值； vcetor<>v 至压入一种数值 并用s[]统计对应糖果数出现次数
*/
const int N=100015;
int a[200010],s[200010];
ll inv_[200010],fac[200010];
ll ans=0;
ll mod= 998244353;
vector<int> v;

ll quick(ll a1,ll b) {
       ll ans=1;
      while(b) {
           if(b&1)
            ans=(a1*ans)%mod;
          a1=(a1*a1)%mod;
          b>>=1;
    }
 return ans;
}
ll inv(ll n){
    return quick(n,mod-2);
}
ll c(int n,int m){
    return fac[n] * inv_[m] % mod * inv_[n - m] % mod;
}
void init() {
    fac[0] = 1;
    for (int i=1; i<=N-10; i++) fac[i]=fac[i-1]*i%mod;
    inv_[N-10]=inv(fac[N-10]);
    for (int i= N-11;i>= 0;i--) inv_[i]=inv_[i+1]*(i+1)%mod;
}

int main()
{
   init();
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   ll n,m;
   int maxn=-1;
   scanf("%lld%lld",&n,&m);
   for(int i=0;i<n;i++){
      scanf("%d",&a[i]);s[a[i]]++;
      maxn=max(maxn,a[i]);
      if(s[a[i]]==1) v.push_back(a[i]);
   }
   for(int i=0;i<maxn-1;i++) printf("0\n");
   for(ll i=maxn;i<=m;i++){
      ans=1;
     for(int j=0;j<v.size();j++){
        ans=(ans*(quick(c(i,v[j]),s[v[j]])))%mod;
     } printf("%lld\n",ans);
   }

    return 0;
}

这篇关于2022-1-7的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！