给定$n$个正整数$a_i$，求出在$\bmod p$意义下$\sum\limits_{i=1}^{n}k^i\cdot a_i^{-1}$

$\texttt{Data Range:}1\leq n\leq 5\times 10^6,2\leq k

链接

题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=5e6+51;
char buf[1<<15],*st=buf,*ed=buf;
ll cnt,mod,k,res,cur;
ll prefix[MAXN],invp[MAXN],num[MAXN];
inline char gcx()
{
    return st==ed&&(ed=(st=buf)+fread(buf,1,32768,stdin),ed==st)?0:*st++; 
}
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=gcx();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=gcx();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=gcx();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=gcx();
    }
    return num*neg;
} 
inline ll qpow(ll base,ll exponent)
{
    ll res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=(li)res*base%mod;
        }
        base=(li)base*base%mod,exponent>>=1;
    }
    return res;
} 
int main()
{
    cnt=read(),mod=read(),k=read(),prefix[0]=1;
    for(register int i=1;i<=cnt;i++)
    {
        prefix[i]=1ll*prefix[i-1]*(num[i]=read())%mod;
    }
    invp[cnt]=qpow(prefix[cnt],mod-2);
    for(register int i=cnt-1;i;i--)
    {
        invp[i]=1ll*invp[i+1]*num[i+1]%mod;
    }
    res=(res+1ll*k*invp[1]%mod)%mod,cur=1ll*k*k%mod;
    for(register int i=2;i<=cnt;i++)
    {
        res=(res+1ll*cur*invp[i]%mod*prefix[i-1]%mod)%mod;
        cur=1ll*cur*k%mod;
    }
    printf("%d\n",res);
}

给定一棵有$n$个节点的带边权树和$q$组询问，第$i$条边的边权为$w_i$。对于每组询问，给定$m$个关键点$k_i$，你要给出一个边集使得割掉这些边会$1$号节点无法到达任意一个关键点。
为了方便，你只需要求出这个边集所包含的边的最小边权就行了。

$\texttt{Data Range}:2\leq 2\leq 2.5\times 10^5,m\geq 1,\sum k_i\leq 5\times 10^5,w_i\leq 10^5$

一共有$T$组数据，每组数据给定一张有$n$个点，$m$条边的无向图，点$i$的类型为$type_i$，其中$type_1$要么为$1$，要么为$2$。一个人想从$s$走到$t$，如果他经过的点$i$中$type_i=1$，则$p_1++$，否则$p_2++$。求出在任何时候，$\vert p_1-p_2\vert\leq k$，为条件下的最短路径。（有点牵强，理解就好）

$\texttt{Data Range:}T\leq 10,n\leq 10^4,m\leq 10^5,k\leq 10$

给定一个长度为$n$的序列$a$,求出$a$的所有子序列中和最大的$k$个的和。

$\texttt{Data Range:}1\leq n\leq 5\times 10^5,1\leq k\leq \min\{\frac{n(n-1)}{2},2\times 10^5\},0\leq a_i\leq 2^32-1$

这里没有珂朵莉的图片啊qwq

给定一个$n$个点$m$条边的无向图和$q$组询问。每组询问给定$k$个二元组$(x_i,y_i)$，求出图上有多少个点$u$与至少一个这次询问的二元组满足$u$到$x_i$的距离小于等于$y_i$。

$\texttt{Data Range:}n\leq 10^3,m\leq 10^5,q\leq 10^5,\sum k\leq 2.1\times 10^6$

题解

生平第一次做Ynoi诶qwq

设$rch_{i,j}$为到$i$的最短距离为$j$的点组成的点集，很显然拿$\texttt{bitset}$维护。

而怎么求$rch_{i,j}$呢？

好像只要跑$n$遍$\texttt{bfs}$就行啦qwq。

给定一个长度为$n$的序列$a$和$q$组询问，对于每组询问，给定$l_1,r_1,l_2,r_2$，求

其中，$\operatorname{get}(l,r,x)$表示在区间$[l,r]$中，数字$x$出现的次数。

注意：答案有可能超过$\texttt{int}$的最大值。

$\texttt{Data Range:}n,q\leq 5\times 10^4,1\leq a_i\leq n,1\leq l_1\leq r_1\leq n,1\leq l_2\leq r_2\leq n$

给定一个只用小写字母组成的串$S$，求出$S$中所有出现次数大于$1$的子串的出现次数与它的长度的乘积的最大值。

$\texttt{Data Range:}\vert S\vert \leq 10^6$

有$n$种食材和$m$位评委。每一位选手要将$n$种食材全部做成满式或汉式料理。如果一位选手做出的菜符合每位评委所喜好的两种菜品中的一种，那么说这位选手是通过考核的。

一共有$T$组数据，对于每组数据，给定$m$位评委所喜好的菜品，问是否有一种做法，使得能通过考核。

$\texttt{Data Range:}T\leq 10,n\leq 100,m\leq 1000$

给定一个串$S$，求$S$中最长的子串$T$，使得可以将$T$分为两个长度大于等于$1$的回文串，只需输出$T$的长度即可。

$\texttt{Data Range:}2\leq \vert S\vert \leq 10^5$

给定整数$n$，求$\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}S(i,j)\times 2^j\times j!\bmod{998244353}$，其中$S(i,j)$为第二类$\texttt{Stirling}$数。

$\texttt{Data Range:}n\leq 10^5$