点击刷新
4361: isn
https://lydsy.com/JudgeOnline/problem.php?id=4361
分析：
dp+容斥。
首先计算出每个长度有多少种子序列是非降的。这一步可以$n^2logn$求出。dp[i][j]表示长度为i的结尾为j的方案数，用树状数组维护。
然后考虑容斥计算答案。长度为i的序列的总共的方案数设为sum[i]，加上所有的操作情况，就是$sum[i] \times (n - i) !$。但是这所有的操作情况中，可能在某个时刻非降了，就要停止。所以减去不合法的。
长度为i的序列，在前一个时刻长度一定是i+1，经过一步多余的操作后长度变成了i，（长度i+1的时候已经合法了）。那么枚举长度i+1时的所有操作情况的序列，再减去一次就是长度为i的答案。因为枚举的是i+1所有的操作情况，可能会出现长度i+1的序列也是不合法的，此时照常减去就行，因为长度为i的序列中，也包含了长度为i+2的时候就合法了的序列（就是因为乘上了那个阶乘），多进行了两步操作后到达的现在的状态，同样包含i+3，i+4...
$Ans=\sum_{i=1}^n(sum[i]\times (n-i)!-sum[i+1]\times (n-i-1)!\times (i+1))$
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<cctype> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 #include<map> 11 #define fi(s) freopen(s,"r",stdin); 12 #define fo(s) freopen(s,"w",stdout); 13 using namespace std; 14 typedef long long LL; 15 16 inline int read() { 17 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; 18 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; 19 } 20 21 const int N = 2005; 22 const LL mod = 1e9 + 7; 23 24 int a[N], disc[N], sum[N], n; 25 LL f[N][N], fac[N]; 26 27 #define add(a,b) (a += b), a > mod ? (a -= mod) : a 28 29 struct BIT{ 30 int sum[N]; 31 void update(int p,int v) { 32 for (; p <= n; p += (p & (-p))) add(sum[p], v); 33 } 34 int query(int p) { 35 int ans = 0; 36 for (; p; p -= (p & (-p))) add(ans, sum[p]); 37 return ans; 38 } 39 }bit[N]; 40 41 int main() { 42 n = read(); 43 for (int i = 1; i <= n; ++i) a[i] = read(), disc[i] = a[i]; 44 45 int cnt = 1; 46 sort(disc + 1, disc + n + 1); 47 for (int i = 2; i <= n; ++i) if (disc[i] != disc[cnt]) disc[++cnt] = disc[i]; 48 for (int i = 1; i <= n; ++i) a[i] = lower_bound(disc + 1, disc + cnt + 1, a[i]) - disc; 49 50 for (int i = 1; i <= n; ++i) f[1][i] = 1ll; 51 for (int i = 2; i <= n; ++i) { 52 bit[i - 1].update(a[i - 1], f[i - 1][i - 1]); 53 for (int j = i; j <= n; ++j) { 54 f[i][j] = bit[i - 1].query(a[j]); 55 bit[i - 1].update(a[j], f[i - 1][j]); 56 } 57 } 58 59 LL ans = 0; 60 fac[0] = 1; 61 for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod; 62 for (int i = 1; i <= n; ++i) 63 for (int j = i; j <= n; ++j) add(sum[i], f[i][j]); 64 65 for (int i = 1; i <= n; ++i) { 66 LL tmp = sum[i] * fac[n - i] % mod - sum[i + 1] * fac[n - i - 1] % mod * (i + 1) % mod; 67 if (tmp < 0) tmp += mod; 68 add(ans, tmp); 69 } 70 cout << ans; 71 72 return 0; 73 }
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
