CF 666C & 牛客 36D

给定字符串S, 求有多少长为$n$的字符串T, 使得S为T的子序列.

可以得到转移矩阵为

$\begin{equation}
A
=\begin{bmatrix}
25 & 0 & 0 &\cdots\ &0 &0\\
1 & 25 & 0 &\cdots\ &0 &0\\
0 & 1 & 25 & \cdots\ & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\
0 & 0 & 0 &\cdots\ &1& 26\\
\end{bmatrix}
\end{equation}$

设$|S|=m$, 答案就为$A^n$的$(m,0)$项, 也就是说答案只与$S$的长度有关, 但是用矩阵幂的话复杂度是$O(m^3logn)$显然过不去.

实际上我们可以直接设$f(n)$为长为$n$的字符串的答案, 不去维护匹配的状态.

可以得到$f(n) = \begin{cases} 0, & n< m \\26f(n-1)+25^{n-m}\binom{n-1}{m-1}, & n\ge m \end{cases}$

前一部分表示在前$n-1$位已经有子序列等于$S$的情形, 那么第$n$位可以任取值.

后一部分表示在第$n$位时第一次出现子序列等于$S$的情形, 那么枚举前$m-1$位在$T$中的第一次出现位置, 其余位置可以任取其余的$25$个值.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+7, P2 = 998244353, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

//head

const int N = 1e5+10;

int t, clk;

char s[N];

vector<pii> g[N];

int ans[N], f[N];

ll p25[N], fac[N], ifac[N];

ll C(int n, int m) {

	return fac[n]*ifac[n-m]%P*ifac[m]%P;

}

int main() {

	p25[0] = fac[0] = ifac[0] = 1;

	REP(i,1,N-1) {

		p25[i] = p25[i-1]*25%P;

		fac[i] = fac[i-1]*i%P;

		ifac[i] = inv(fac[i]);

	}

	scanf("%d%s", &t, s);

	int now = strlen(s);

	REP(i,1,t) {

		int op, x;

		scanf("%d", &op);

		if (op==1) scanf("%s", s), now = strlen(s);

		else scanf("%d", &x), g[now].pb(pii(x,++clk));

	}

	REP(i,1,N-1) if (g[i].size()) {

		sort(g[i].begin(),g[i].end());

		int sz = g[i].size(), now = 0;

		while (now<sz&&g[i][now].x<i) ++now;

		f[i-1] = 0;

		REP(j,i,N-1) {

			f[j] = (f[j-1]*26ll+C(j-1,i-1)*p25[j-i])%P;

			while (now<sz&&g[i][now].x==j) ans[g[i][now++].y] = f[j];

			if (now>=sz) break;

		}

	}

	REP(i,1,clk) printf("%d\n",ans[i]);

}

巴特西

CF 666C & 牛客 36D

最新文章

热门文章