E. Tyler and Strings（组合计数 + 树状数组/线段树）（带重复元素的全排列）

题目链接

主要思路还是比较好想的，一些细节公式预处理比较难搞…

参考题解

分析

从前往后遍历，如果s[]剩下的数中，s[i] < t[i]则对答案是有贡献的；
贡献就是后面位置[i+1 ~ n]的数字可以随便排，也就是带重复数字的全排列（公式看题解）；
到这里就知道了要搞一个桶来维护一下每个数字的个数，而且要维护前缀和。

计算完第i位，向后遍历时，我们的s[i]就要=t[i]了，因此每次剩下的数字中cnt[s[i]]要–；
因此动态修改查询我们可以用树状数组或线段树维护这个桶。

关键是你每次修改了cnt的话，你后面的全排列计算公式也是不一样的，这个咋搞？
我们可以一开始可以先求出公式中的分母部分(记得逆元)mu；
对于每次修改，在修改前我们先把mu除掉cnt[s[i]]，cnt[s[i]]–，然后mu再乘上cnt[s[i]]就行了；

注意最后我们还要特判s[]是t[]的前缀的情况，此时ans += 1；
题解中是从0开始的，因此是 fac[n-i-1]；
我是从1开始的，所以fac[n-i]，这个注意一下就行。

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// #include 
#include
#include
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"< PII;
typedef pair PDI;
typedef pair PLL;
typedef pair PDD;
typedef pair > PDID;
typedef pair PCC;
typedef pair > PCII;
typedef pair > PIII;
typedef pair > > PIIII;
typedef pair > PLII;

const int maxn = 2e5 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 998244353;
//const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int s[maxn],t[maxn];
int cnt[maxn];	//s[]中每种数的个数
ll fac[maxn],infac[maxn];	//阶乘，阶乘逆元
int n,m;

struct node
{
	int l,r;
	ll v;
}tr[maxn*4];

void pushup(int u)
{
	tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
//	tr[u].v = max(tr[u<<1].v, tr[u<<1|1].v);
}

void build(int u,int l,int r)
{
	tr[u] = {l,r};
	
	if(l == r) return;

	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

void update(int u,int idx,int x)	//单点修改
{
	if(tr[u].l == idx && tr[u].r == idx)
	{
		tr[u].v += x;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(idx <= mid) update(u<<1, idx, x);
	else update(u<<1|1, idx, x);
	
	pushup(u);
}

int query(int u,int l,int r)
{
	if(l <= tr[u].l && r >= tr[u].r) return tr[u].v;
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	int ans = 0;
	if(l <= mid) ans += query(u<<1, l, r);
	if(r > mid) ans += query(u<<1|1, l, r);
	
	return ans;
}

void init()	//处理阶乘和阶乘逆元
{
	fac[0] = infac[0] = 1;
	for(int i=1;i
		fac[i] = fac[i-1] * i % mod;
		infac[i] = infac[i-1] * qmi(i,mod-2,mod) % mod;
	}
}

void solve()
{
	init();
	
	iire(n,m);
	
	build(1,1,maxn-1);	//注意这里是maxn-1，不是n
	
	for(int i=1;i<=n;i++)
	{
		ire(s[i]);
		cnt[s[i]]++;
		
		update(1,s[i],1);
	}
	
	for(int i=1;i<=m;i++) ire(t[i]);
	
// 	cout<
		ll num = query(1,1,t[i]-1);	//求出s[]剩下数字中
			mu = mu * fac[cnt[t[i]]] % mod;	//先除去cnt[t[i]]
			cnt[t[i]] --;
			mu = mu * infac[cnt[t[i]]] % mod;	//先乘上cnt[t[i]]
			
			update(1,t[i],-1);
		}
		else
		{
			f = 0;
			break;
		}
	}
	
	if(f && n < m) ans = (ans + 1) % mod;	//s是t的前缀
	
	cout<
	int T;
//	ire(T);
	T = 1;
	while(T--)
	{
		solve();
	}
	
	return 0;
}

E. Tyler and Strings（组合计数 + 树状数组/线段树）（带重复元素的全排列）

C/C++/C#相关栏目本月热门文章