题目:
问 \(m\)(\(m\) 任取)个正整数组成的 \(a\) 数组按照题目操作可构造的长度为 \(n\) 值域为 \([1,x]\) 的集合数量。
题目操作为:\(s=\sum_{i=1}^m a_i\),把 \(s-a_i\) 插入集合。
推点性质
1
集合有无序性,令集合内升序排序,可以代表这个集合。
\(a\) 也有无序性,所以也升序排序。(具体的 \(a_i\le a_{i+1}\))
2
考虑增量:
如果新加入的 \(a_i\) 之前出现过,则不会增加集合元素,只会让集合整体加 \(a_i\)。
如果没出现过,则会让集合整体加 \(a_i\) 后加入 \((\sum_{j=1}^i a_j) -a_i\)。
3
首先看到 \(s-a_i\) 容易想到差分,发现:
若 \(a\) 不重,那么 \(a\) 的差分数组和集合的差分数组是一样的。
若 \(a\) 有重,\(a\) 去完重后的差分数组和集合的差分数组还是一样的,因为重的 \(a_i\) 只会影响 \(s\)。所以下面我们均维护去重后的 \(a\),而重复的 \(a_i\) 会体现为全局加。
4
构造 \(a_1=1\) 的 \(a\),集合最大值为 \(s-1\),对应的合法原数组数量为 \(x-(s-1)+1\)。(同时也可知 \(s\le x+1\) 的范围。)
于是有个暴力 DP:
\(f_{i,j,k}\):构造 \(a_1=1,\left | a \right |=i,s=j,a_i=k\) 的方案数。
转移 \(O(nx^3)\)。(实际上判掉无解是 \(O(\sqrt x x^3)\))
5
思考如何优化性质 \(4\) 的 DP,考虑去掉 \(k\) 这一维,我们定义两种操作:
- 在 \(a\) 序列前拼接 \(1\),
- \(a\) 序列整体 \(+1\)。
我们发现这样很好维护递增的条件了,并且我们也不用枚举新拼接的数,因为我们可以类似完全背包地考虑到每个新拼接的数。
\(f_{i,j,0/1}\):\(\left | a \right | =i,s=j\),\(a_1\) 是否有 \(1\)。
6
由于 \(s\le x+1\) 且我们 DP 的是无重复元素的 \(a\),所以 \(\frac{(1+n)n}{2}\le x+1\) 时,\(f_n\) 才会有值。
判完无解复杂度为 \(O(\sqrt x x)\)。
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x;
}
void xie(int x,int shen=0)
{if(!x){if(!shen) putchar('0');return ;}xie(x/10,1);putchar('0'+x%10);
}
const int QAQ=2e5+7,mo=998244353;
int t,n,x,dp[QAQ][2];
signed main()
{t=read();for(int i1=1;i1<=t;i1++){n=read(),x=read();if(n==1) {xie(x),putchar('\n');continue;}if(n*(n-1)/2>x+1) {puts("0");continue;}for(int i=0;i<=x+1;i++) dp[i][0]=dp[i][1]=0;dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=x+1;j++) dp[j][1]=dp[j-1][0];for(int j=0;j<=x+1;j++)if(j<i) dp[j][0]=0;else dp[j][0]=(dp[j-i][0]+dp[j-i][1])%mo;}int ans=0;for(int i=1;i<=x+1;i++) ans=(ans+dp[i][1]*(x-i+2)%mo)%mo;xie(ans);putchar('\n');}return 0;
}