[结论 + 组合] UOJ144. 【UER #5】万圣节的糖果

神结论题...太菜了根本想不到啊...

有结论可以把奇偶性不同转化为相同:

\(f(i,j,k)\) 表示原题条件情况下,放了 \(1\)\(n\) ,有 \(j\) 个集合末尾奇偶和 \(i\) 相同,\(k\) 个奇偶性不同。

\(dp(i,j,k)\) 表示相同集合奇偶相同的情况,定义同上。显然这个可以 \(O(n^2)\) 求。

有结论 \(f(i,j,k)=dp(i+1,k+1,j)\) ...

证明:

一个数 \(x\) 只要不是所在集合内的最大数,就会有一个前驱(就是所在集合内最小的比它大的数)。

我们添加一个单元集 \(\{i+1\}\)

然后对于一个数 \(x\) , 如果它是所在集合内最大数就不动,否则就令它的前驱为原来的前驱加一。

我们可以从大到小枚举每一个数,这样依次定下每个数后来的位置,就得到了一个同集合奇偶相同的分拆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int P=998244353;
int n,m,f[3015][6015];
LL ans;
int main(){
freopen("uoj144.in","r",stdin);
freopen("uoj144.out","w",stdout);
scanf("%d%d",&n,&m);
f[0][0]=1;
for(int i=1;i<=n/2+2;i++){
f[i][0]=0;
for(int j=1;j<=i;j++) f[i][j]=(f[i-1][j-1]+(LL)f[i-1][j]*j%P)%P;
}
for(int i=0;i<=m;i++)
ans=(ans+(LL)f[(n+1+1)/2][m-i+1]*f[(n+1)/2][i]%P)%P;
for(int i=1;i<=m;i++) ans=ans*i%P;
printf("%lld\n",ans);
return 0;
}