[ARC043B]難易度

想到统计有多少个一位 \(\to\) 多少个二位 \(\to\) 多少个三位 \(\to\) 多少个四位。

注意：这里的“一位”、“二位”指的是作为一位、二位的情况数。 也就是说，对于 1 2 4 5 10 来说，\(4\) 可以在 1 2 4 里作为三位，也可以在 1 4 10 中作为二位。这都要被统计在内。

• 多少个一位？所有的都可以作为一位。当然后三个数不行，但那并不重要。
• 多少个二位？
  • 这需要 dp。设 \(dp_i\) 表示难度为 \(i\) 的数能作为几个二位——上面的 \(4\) 是在 1 4 10 里作为二位，还是在 2 4 10 里作为二位？
  • 怎么 dp？设 \(cnt_i\) 为 \(D_i\) 的桶，\(dp_i=\sum\limits_{j=1}^{i/2} dp_j \times cnt_i\)。这件事情显然可以前缀和做。
• 多少个三位？方法同上，我们的 dp 变成了二维的：\(dp_{i,j}\) 表示难度为 \(i\) 的数能作为几个 \(j\) 位？当然，具体实现时，我们可以滚动数组压掉一维。

那么我们只需要把第二个 \(\circ\) 里的事情做 3 遍——二位、三位、四位。最后加起来所有的 \(dp_i\)。

代码如下：

#include 
#include 

typedef long long lint;
const int N=1e5+10;
const int mod=1e9+7;

int dp[N],s[N],t[N];

int main() {
	int n,V=0;
	scanf("%d",&n);
	for(int i=1,x; i<=n; i++) {
		scanf("%d",&x);
		dp[x]++,t[x]++;
		V=std::max(V,x);
	}
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=V; j++) {
			s[j]=(lint)(s[j-1]+dp[j])%mod;
			dp[j]=(lint)s[j/2]*t[j]%mod;
		}
	}
	int ans=0;
	for(int i=1;i<=V;++i)
		ans=(lint)(ans+dp[i])%mod;
	printf("%d\n",ans);
	return 0;
}

THE END