BZOJ4402 Claris的剑 注意到 " 我们认为两把剑本质不同，当且仅当存在至少一个宽度，在两把剑的宽度序列里面出现次数不一样 " 冷静分析后发现，我们可以根据字典序最小来构造序列 或者从另一方面想：将某些剑重新排列后，跟以下两种本质相同 1. 1 ( 2 , 1 ) ( 2 , 1 ) ( 2 , 1 ) . . . 2 ( 3 , 2 ) . . . 3 ( 4 , 3 ) . . . m 1(2,1)(2,1)(2,1)...2(3,2)...3(4,3)...m 1(2,1)(2,1)(2,1)...2(3,2)...3(4,3)...m 2. 1 ( 2 , 1 ) ( 2 , 1 ) ( 2 , 1 ) . . . 2 ( 3 , 2 ) . . . 3 ( 4 , 3 ) . . . m , m − 1 1(2,1)(2,1)(2,1)...2(3,2)...3(4,3)...m, m-1 1(2,1)(2,1)(2,1)...2(3,2)...3(4,3)...m,m−1 考虑枚举最后的 m，也就是钦定序列的最大值，然后将二元组插入序列，是一个经典的插板问题 如果最后的长度为 n，最大值为 m，那么方案数为 ( n − m 2 + m − 1 m − 1 ) + ( n − m − 1 2 + m − 1 m − 1 ) \binom{\frac{n-m}{2}+m-1}{m-1}+\binom{\frac{n-m-1}{2}+m-1}{m-1} (m−12n−m+m−1)+(m−12n−m−1+m−1) 于是有 O ( n ∗ m ) O(n*m) O(n∗m) 的做法，就是枚举最后的最大值与长度 考虑直接枚举 n − m 2 \frac{n-m}{2} 2n−m a n s = ∑ i = 1 m ∑ j = 1 n − i 2 ( i + j − 1 − 1 i − 1 − 1 ) + ∑ i = 1 m ∑ j = 1 n − i − 1 2 ( i + j − 1 − 1 i − 1 − 1 ) ans=\sum_{i=1}^m\sum_{j=1}^{\frac{n-i}{2}}\binom{i+j-1-1}{i-1-1}+\sum_{i=1}^m\sum_{j=1}^{\frac{n-i-1}{2}}\binom{i+j-1-1}{i-1-1} ans=i=1∑mj=1∑2n−i(i−1−1i+j−1−1)+i=1∑mj=1∑2n−i−1(i−1−1i+j−1−1) = ∑ i = 1 m ( i + n − i 2 − 1 i − 1 ) + ∑ i = 1 m ( i + n − i − 1 2 − 1 i − 1 ) =\sum_{i=1}^m\binom{i+\frac{n-i}{2}-1}{i-1}+\sum_{i=1}^m\binom{i+\frac{n-i-1}{2}-1}{i-1} =i=1∑m(i−1i+2n−i−1)+i=1∑m(i−1i+2n−i−1−1) 于是就可以 O ( m ) O(m) O(m) 了
#include<bits/stdc++.h> #define N 2000050 using namespace std; const int Mod = 1e9 + 7; typedef long long ll; ll add(ll a, ll b){ return (a + b) % Mod;} ll mul(ll a, ll b){ return (a * b) % Mod;} int n, m; ll fac[N], inv[N]; ll calc(int x, int y){ x >>= 1; --y; return mul(fac[x + y], mul(inv[x], inv[y])); } int main(){ scanf("%d%d", &n, &m); ll ans = n && m; m = min(n, m); fac[0] = fac[1] = inv[0] = inv[1] = 1; for(int i = 2; i <= n; i++) fac[i] = mul(fac[i-1], i), inv[i] = mul(Mod-Mod/i, inv[Mod%i]); for(int i = 2; i <= n; i++) inv[i] = mul(inv[i], inv[i-1]); for(int i = 2; i <= m; i++) ans = add(ans, add(calc(n-i, i), calc(n-i-1, i))); cout << ans; return 0; }