开源手机网站建站系统/百度秒收录

传送门

首先可以猜测复杂度n^2*m以及猜测做法是dp，但这并没有卵用。

最直观的想法自然是dp[i][v1][v2]，这一次同时决策出a[i]=v1，b[i]=v2。但直接转移复杂度是n^4*m，因为我们拿这个看上去像卷积形式的转移方程没啥办法。如果把第3维用前缀和优化一下，复杂度是n^3*m，仍然没法过。

所以我们需要先分析一下性质。a数组单增，b数组单减，a[i] <= b[i]，于是有a[j] <= a[i] <= b[i] <= b[j]，1 <= j <= i。所以在a数组单增和b数组单减都满足的前提下，我们只需要保证a[i] <= b[i]，前面的下标都不用管。于是我们可以先单独求出合题意的a数组和b数组的数目，再进行合成。

定义dp[0/1][i][j]为：0、1表示a、b数组，i个数且末尾值为j的数目。dp[0]和dp[1]分开处理即可。

最后求ans，只需要枚举第m个元素的值v1和v2，使用乘法原理来求贡献。
妙啊！

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e3 + 5,mod = 1e9 + 7;int n,m,dp[2][13][N];void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {cout << f << " ";dbg(r...);
}
template<typename Type>inline void read(Type &xx){Type f = 1;char ch;xx = 0;for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';xx *= f;
}int main(int argc, char** argv) {read(n);read(m);rep(u,0,1) rep(j,1,n) dp[u][1][j] = 1;rep(i,2,m){rep(j,1,n){rep(k,0,j){(dp[0][i][j] += dp[0][i-1][k]) %= mod;}dwn(k,n,j){(dp[1][i][j] += dp[1][i-1][k]) %= mod;}}}int ans = 0;rep(v1,1,n) rep(v2,v1,n){(ans += 1LL * dp[0][m][v1] * dp[1][m][v2] % mod) %= mod;}printf("%d\n",ans);return 0;
}