省流：\(100 + 100 + 100 + 10\)。四道数数太好玩了。绿蓝紫黑。
T1
题意：
如下是一个不完全正确的归并排序算法代码。
//此函数表示将S[1,mid],S[mid+1,r]两个有序序列合并成为一个大的有序序列S[l,r]，如果原序列无序则合并后的序列也无序
void merge_arr(int l,int mid,int r)
{
//merge_array
}
void merge_sort(int l,int r,int deep)
{
if(l==r) return;
if(deep>=K) return;
int mid=(l+r)>>1;
merge_sort(l,mid,deep+1);
merge_sort(mid+1,r,deep+1);
merge_arr(l,mid,r);
}
其中，主函数内将使用如下方法调用排序：
merge_sort(1,n,0);
初始给定一个 \(n\) 表示你要给一个长度为 \(n\) 的排列进行排序，多次询问，每次给定一个 \(k\)，你需要求出有多少种排列能够用上面的代码排序成单调递增的，对 \(998244353\) 取模。
\(T \leq 100,n \leq 5 \times 10^6,k \leq 10^9\)。
容易发现，对于一个 \(k\) 和一个排列，第 \(k\) 层的每个区间内排列中的数字都单调递增，则这个排列是可以排序好的。设第 \(k\) 层的区间为 \([l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]\)（这些区间并为 \([1,n]\)，交为空），那么合法的排列个数即为 \(\frac{n}{\prod_{i = 1}^m r_i - l_i + 1}\)。容易发现同一层中区间不同长度至多为 \(2\)，所以可以递推得出第 \(k\) 层中长度为 \(x\) 的有多少个区间，计算上述柿子即可。对于 \(k > \log n\)，那么不管什么排列都合法，输出 \(n!\) 即可。
时间复杂度 \(\Theta(n + T)\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=24,p=998244353;
int t,n,a[N],dp[N][2],ans[N],fac[1<<N],inv[1<<N];
int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
void init(int lim) {
fac[0]=inv[0]=1;
for(int i=1; i<=lim; i++) fac[i]=fac[i-1]*i%p;
inv[lim]=qpow(fac[lim],p-2);
for(int i=lim-1; i>=1; i--) inv[i]=inv[i+1]*(i+1)%p;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t>>n;
init(n);
int tmp=n,tot=0;
while(tmp) {
a[++tot]=tmp;
tmp/=2;
}
dp[1][0]=1;
for(int i=2; i<=tot; i++) {
if(a[i-1]&1) dp[i][0]=(dp[i][0]+dp[i-1][0])%p,dp[i][1]=(dp[i][1]+dp[i-1][0]%p+2*dp[i-1][1]%p)%p;
else dp[i][0]=(dp[i][0]+2*dp[i-1][0]%p+dp[i-1][1])%p,dp[i][1]=(dp[i][1]+dp[i-1][1])%p;
}
for(int i=1; i<=tot; i++) ans[i]=fac[n]*qpow(inv[a[i]],dp[i][0])%p*qpow(inv[a[i]+1],dp[i][1])%p;
while(t--) {
int k;
cin>>k;
if(k>=tot) cout<<fac[n]<<'\n';
else cout<<ans[k+1]<<'\n';
}
return 0;
}
T2
题意：给定正整数 \(n,m\)，以及长度为 \(m\)，值域为 \([0,n−1]\) 的整数序列 \(a_1,a_2,\cdots,a_m\)。保证 \(a\) 中元素互不相同。
你需要计算满足以下要求的 \(0,1,…,n − 1\) 的排列 \(p\) 的数量：
-
能够经过任意次以下操作，使 \(p=a\)：
- 选择 \(1 \leq l \leq r\leq \lvert p \rvert\) 的两个数 \(l,r\)，如果 \(\text{mex}({p_l,p_{l + 1},…,p_r})\) 存在于序列 \(p\) 中，则将 \(p_l,p_{l + 1},\cdots,p_r\) 删除。
输出答案对 \(998244353\) 取模后的结果。
\(1 \leq m \leq n \leq 10^6,\sum m \leq 10^6,0 \leq a_i <n\)，\(a\) 中元素互不相同。
注意，\(\sum a\) 没有限制。
将排列 \(p\) 合法的要求转换一下，设 \(a\) 中最小的元素为 \(mn\)，设 \(l,r\) 为对于 \(p\) 中所有 \(<mn\) 的元素位置最小和最大的位置是什么，则合法要求为 \(p\) 中 \(a\) 的元素按照顺序且不存在一个 \(a\) 中的元素它的位置 \(>l\) 且 \(<r\)。
我们可以先钦定 \(mn + m\) 个位置表示这些位置用来放 \(<mn\) 的元素和 \(a\) 中的元素，方案数为 \(C_n^{mn + m}\)，由于 \(a\) 中的元素不能 \(>l\) 且 \(<r\)，所以对于这 \(mn + m\) 个位置分配的方案数为 \(m + 1\)，由于 \(<mn\) 的元素可以乱序，方案数为 \(mn!\)，最后再把剩下的 \(n - mn - m\) 放进去，方案数为 \((n - mn - m)!\)，把以上所有的方案数相乘即是答案。\(mn \leq 1\) 可能需要特判。
时间复杂度 \(\Theta(n + \sum m)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,p=998244353;
int t,n,m,fac[N],inv[N];
inline int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=1ll*ans*a%p;
a=1ll*a*a%p;
b>>=1;
}
return ans;
}
inline void init(int lim) {
fac[0]=inv[0]=1;
for(int i=1; i<=lim; i++) fac[i]=1ll*fac[i-1]*i%p;
inv[lim]=qpow(fac[lim],p-2);
for(int i=lim-1; i>=1; i--) inv[i]=1ll*inv[i+1]*(i+1)%p;
}
inline int C(int n,int m) {
if(n<m||n<0||m<0) return 0;
return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;
}
inline int read() {
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=1ll*x*10+ch-'0',ch=getchar();
return x;
}
void write(int x) {
if(x>=10) write(x/10);
putchar(x%10+'0');
}
int main() {
init(1e6);
t=read();
while(t--) {
n=read(),m=read();
int mn=INT_MAX;
for(int i=1; i<=m; i++) {
int x;x=read();
mn=min(mn,x);
}
if(mn<=1) {
write(1ll*fac[n]*inv[m]%p);putchar('\n');
continue;
}
write(1ll*C(n,m+mn)*(m+1)%p*fac[mn]%p*fac[n-m-mn]%p);putchar('\n');
}
return 0;
}
T3
题意：给定一张 \(n\) 个点 \(m\) 条边的图和一个定值 \(k\)，你需要对所有的 \(0 \leq i \leq k\) 求出只保留 \(n - 1 + i\) 条边且图还连通的选边方案数，对 \(998244353\) 取模。
\(n \leq 17,0 \leq k \leq 2\)。
这个 \(k\) 的范围非常有迷惑性，实际上树和基环树的性质完全没有用。
可以设计状压 dp，设 \(dp_{state,0/1/2}\)，表示当前已经连通了 \(state\) 的二进制位中为 \(1\) 的点，且保留了 \(\text{popcount}(state) + 0/1/2\) 条边。转移如下：
\[dp_{state,0} = \sum_{s \in state} cnt_{s,state \oplus s} \times dp_{s,0} \times dp_{state \oplus s,0} \\ dp_{state,1} = dp_{state,0} \times (n - \text{popcount}(state) + 1) + \\ \sum_{s \in state} cnt_{s,state \oplus s} \times (dp_{s,1} \times dp_{state \oplus s,0} + dp_{s,0} \times dp_{state \oplus s,1}) \\ dp_{state,2} = dp_{state,1} \times (n - \text{popcount}(state)) + \\ \sum_{s \in state} cnt_{s,state \oplus s} \times (dp_{s,2} \times dp_{state \oplus s,0} + dp_{s,0} \times dp_{state \oplus s,2} + dp_{s,1} \times dp_{state \oplus s,1}) \]\(cnt_{s,t}\) 表示一个端点在 \(s\) 中，另一个端点在 \(t\) 中的边的个数。
发现这会算重，但是容易发现上述的 dp 对于一个有 \(i\) 条边的图，对于每一条边都会给答案加上这张图的贡献，所以让 \(dp_{state,0}\) 除以 \(\text{popcount}(state)-1\)，\(dp_{state,1/2}\) 同理即可。
这样我们就得到了一个 \(\Theta(3^n n^2)\) 的做法。考虑优化，发现一条边两个端点有一个不在 \(state\) 中，那么这条边无论如何都不会算到，可以暴力算出有可能被算到的边，记数量为 \(sum\)，如果一条边两个端点都在 \(state\) 中但却没有计算到当且仅当两个端点都在 \(s\) 或 \(state \oplus s\)，于是先预处理高维前缀和，这样我们就可以快速的求出 \(cnt_{s,t} = sum - tot_s - tot_t\)。
时间复杂度 \(\Theta(2^n n^2 + 3^n)\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300,p=998244353;
int n,m,k,u[N],v[N],dp[200005][3],sum[200005];
inline int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=1ll*ans*a%p;
a=1ll*a*a%p;
b>>=1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>k;
for(int i=1; i<=m; i++) cin>>u[i]>>v[i],sum[(1<<u[i]-1)|(1<<v[i]-1)]++;
for(int i=0; i<n; i++) for(int j=0; j<(1<<n); j++) if(j&(1<<i)) sum[j]+=sum[j^(1<<i)];
for(int i=1; i<(1<<n); i++) {
if(__builtin_popcount(i)==1) dp[i][0]=1;
else {
int cnt=0;
for(int j=1; j<=m; j++) if((i&(1<<u[j]-1))&&(i&(1<<v[j]-1))) cnt++;
for(int s=i&(i-1); s; s=(s-1)&i) if(s<(i^s)) dp[i][0]=(dp[i][0]+(cnt-sum[s]-sum[i^s])*(dp[s][0]*dp[i^s][0]%p)%p)%p;
dp[i][0]=dp[i][0]*qpow(__builtin_popcount(i)-1,p-2)%p;
for(int s=i&(i-1); s; s=(s-1)&i) if(s<(i^s)) dp[i][1]=(dp[i][1]+(cnt-sum[s]-sum[i^s])*(dp[s][1]*dp[i^s][0]%p+dp[s][0]*dp[i^s][1]%p)%p)%p;
dp[i][1]=(dp[i][1]+dp[i][0]*(cnt-__builtin_popcount(i)+1)%p)%p;
dp[i][1]=dp[i][1]*qpow(__builtin_popcount(i),p-2)%p;
for(int s=i&(i-1); s; s=(s-1)&i) if(s<(i^s)) dp[i][2]=(dp[i][2]+(cnt-sum[s]-sum[i^s])*(dp[s][2]*dp[i^s][0]%p+dp[s][0]*dp[i^s][2]%p+dp[s][1]*dp[i^s][1]%p)%p)%p;
dp[i][2]=(dp[i][2]+dp[i][1]*(cnt-__builtin_popcount(i))%p)%p;
dp[i][2]=dp[i][2]*qpow(__builtin_popcount(i)+1,p-2)%p;
}
}
for(int i=0; i<=k; i++) cout<<dp[(1<<n)-1][i]<<'\n';
return 0;
}
闲话：这题其实没有 \(100\)，被卡常了，但是通过死缠烂打让教练把时限开到了 2s 于是过了/kx
T4
原题：qoj8143。
首先暴力求出 \(\sum_{i=1}^b f(a,b,i)\)，接下来讨论 \(i > b\) 的情况。
若 \(a \mid b\)，则 \(i > b\) 时答案为 \(\frac{b}{a}\)，接下来不做讨论（即不讨论下文方程中 \(y = 0\) 的情况）。
显然 \(f(a,b,i)\) 为方程 \(ax + iy = b\) 的解中最小的非负整数解 \(x\)，将方程变形为 \(x = \frac{b − iy}{a}(x \geq 0)\)。由于 \(i>b\)，有 \(\lvert iy \rvert > b\)，又因为 \(x \geq 0\)，所以 \(y < 0\)。设 \(z = −y(z > 0)\)，则 \(x=\frac{b + iz}{a}\)，由于最小化 \(x\)，则 \(z\) 取 \(f(i,−b,a)\)。发现若 \((i ~\text{mod}~ a)\) 相同时，取得的 \(z\) 也相同。枚举 \((i ~\text{mod}~ a)\)，等差数列求和即可。
设 \(l = a + b\)，单组数据总时间复杂度 \(\Theta(l \log l)\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353;
int t,n,a,b;
int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
void exgcd(int a,int b,int &x,int &y) {
if(!b) {
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int solve(int a,int c,int b) {
int d=__gcd(a,b);
if(abs(c)%d) return -1;
a/=d,b/=d,c/=d;
int x,y;
exgcd(a,b,x,y);
return (x*c%b+b)%b;
}
int calc(int fir,int lst,int len) {return (fir+lst)%p*(len%p)%p*499122177%p;}
signed main() {
cin>>t;
while(t--) {
int ans=0;
cin>>n>>a>>b;
for(int i=1; i<=min(b,n); i++) ans=(ans+(solve(a,b,i)==-1?0:solve(a,b,i)))%p;
if(b%a==0) {
cout<<(ans+(b/a)*((n-min(b,n))%p)%p)%p<<endl;
continue;
}
if(n>b) {
for(int i=0; i<a; i++) {
int fir=(b/a*a+i<=b?b/a*a+i+a:b/a*a+i),lst=(n/a*a+i>n?n/a*a+i-a:n/a*a+i),len=(lst-fir)/a+1;
if(len<=0) continue;
int z=solve(i,-b,a);
if(z==-1) continue;
ans=(ans+(len*b%p+calc(fir,lst,len)*z%p)%p*qpow(a,p-2)%p)%p;
}
}
cout<<ans<<endl;
}
return 0;
}