9.3模拟赛
t1
小 A 是一个爱好排列的女孩子，如果一个排列 P 满足对于所有的 i 都有：| Pi -i | ≠\neq = k。那么我们就称排列 P 是可爱的。 对于小 A 给定的 n 和 k，请问有多少种不同的可爱的排列？ 因为这个数量实在太大了，请输出答案对 998244353 取模后的结果。
``
我们将每个不合法的i和他放在哪个位置不合法连一条边 这样发现是会形成很多条链
我们是搞两列连边 这样有2*n条链
我们相当于开个数组当每一条链连起来 然后当i==j的时候就相当于一条链的开头 不能和前面的链相连
然后我们考虑容斥 即g[i]表示有i个点不合法的方案数
这样直接容斥即可
然后考虑如何求解g[i]
我们用f[i][j][0/1]表示前i条不合法的边选了j条边的方案数0表示当前边不选 1表示当前边选 转移的话就是f[i][j][0]=(f[i-1][j][1]+f[i-1][j][0])
因为相邻的边就代表在同一个点放两个东西 所以f[i][j][1]=(f[i-1][j-1][0])
因为每一个不同的方案那些一定合法的可以换地方所以要乘一个阶乘
(f[n<<1][0][0]+f[n<<1][0][1])*fac[n]就相当于全排列
`
#include <cstdio>
#include <algorithm>
#define ll long long
#define N 2008
#define mod 998244353
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int f[N<<1][N<<1][2],link[N<<1],fac[N<<1];
int main()
{
// setIO("input");
int i,j,n,k,tot=0;
scanf("%d%d",&n,&k);
fac[0]=1,f[0][0][0]=1;
for(i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%mod;
for(i=1;i<=k;++i)
{
for(int t=1;t<=2;++t)
for(j=i;j<=n;j+=k)
if(j!=i) link[++tot]=1; else ++tot;
}
for(i=1;i<=tot;++i)
{
for(j=0;j<=n;++j)
{
f[i][j][0]=(ll)(f[i-1][j][0]+f[i-1][j][1])%mod;
if(link[i]) f[i][j][1]=f[i-1][j-1][0];
}
}
int ans=0;
for(i=0;i<=n;++i)
{
int tmp=(ll)(f[n<<1][i][0]+f[n<<1][i][1])%mod;
tmp=(ll)tmp*fac[n-i]%mod;
if(i&1) ans=(ll)(ans-tmp+mod)%mod;
else ans=(ll)(ans+tmp)%mod;
}
printf("%d\n",ans);
return 0;
}
t2
小 B 是一个辛勤的农民，他家里种了一棵很大的苹果树。
这棵苹果树可以看作一张 n 个点 n-1 条边的无向连通图，小 B 觉得这颗苹果树很脆弱， 因为只要剪断任意一条边，苹果树就不连通了，于是他给苹果树新加了 m 条边。
现在这颗苹果树就不像是一棵树了，成了一张 n 个点 n+m-1 条边的无向连通图，小 Q 是小 B 的好朋友，他觉得这棵树依然很脆弱，他告诉小 B，自己只要破坏两条边，一条是原树中的边，一条是小 B 新加的边，就能使苹果树不连通。
小 B 觉得小 Q 说得很不可思议，于是他找来了擅长编程的你，希望你告诉他，按照小 B 的破坏规则，有多少种不同的方案使得苹果树不连通。
注意：两种方案不同当且仅当一条边在第一种方案中被删除了但在第二种方案中没有被 删除。
树上差分 每多一条非树边就把所有他覆盖的树边加1 如果一条边没有被覆盖就可以删任意非树边 有一条就可以删这一条 否则就不行
t3
温神不喜欢括号序列，但是他发现总是有人喜欢出括号序列的题。
为了让全世界都能感受到他的痛苦，他想要写一个转换器：它能把普通的小写字符串转换成长度相同的合法的括号序列。
在温神的构思中，这样的转换器需要满足如下两个条件：
结果的括号序列必须要是合法的，即左右括号必须要是相匹配的。
对于一对相匹配的左右括号，他们所在的位置原来的小写字母必须相同。
举例来说，对于字符串 aabaab，()(()) 就是一个合法的答案，而 ()()() 不满足第二个条件，(((())不满足第一个条件。
温神发现，不是对于所有的小写字符串，都存在满足条件的转化方案。于是她给出了一个字符串 s，她想要知道有多少个区间 [l,r]，满足区间 [l,r] 形成的字符串存在每组条件的转化方案。
对于 20% 的数据，|s|≤20。 对于 40% 的数据，|s|≤500。 对于 70% 的数据，|s|≤5000。 对于 100% 的数据，|s|≤1e6。
暴力是开一个栈来匹配
然后发现如果（1，i）和（1，j）的栈内括号一质 就说明i+1,j这区间的可以匹配消除 因为要求的是所有子序列 一个i满足的j可能有多个 所以map记录个数统计答案
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
typedef long long ll;
char s[N],sta[N];
ll top=0,hash1,hash2,p1=131,p2=13331,len;
ll pow1[N],pow2[N];
map<ll,ll>mp;
int mod=1000007;
int main()
{
scanf("%s",s+1);
len=strlen(s+1);
long long ans=0;
pow1[0]=1,pow2[0]=1;
for (long long i=1;i<=len;i++) pow1[i]=pow1[i-1]*p1%mod,pow2[i]=pow2[i-1]*p2%mod;
mp[0]=1;
for (long long i=1;i<=len;i++)
{
if(!top||sta[top]!=s[i])
{
sta[++top]=s[i];
hash1+=pow1[top]*(s[i]-'a'+1)%mod;hash1%=mod;
hash2+=pow2[top]*(s[i]-'a'+1)%mod;hash2%=mod;
}
else
{
hash1+=mod-pow1[top]*(s[i]-'a'+1)%mod;hash1%=mod;
hash2+=mod-pow2[top]*(s[i]-'a'+1)%mod;hash2%=mod;
top--;
}
ans+=mp[hash1*mod+hash2];
mp[hash1*mod+hash2]++;
}
printf("%lld\n",ans%998244353);
}