链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4361
数据传送门:http://oi.cyo.ng/?attachment_id=1898
题解
考虑一个长度为i的非下降子序列
如果忽略成为非下降子序列就停止的限制
那么其对于答案的贡献为g[i]*(n-i)!
现在考虑成为非下降子序列就停止的限制
对于长度为i的非下降子序列,非法的话,一定是从i+1的序列删掉一个数
所以减掉\(g[i + 1] \cdot (n – (i + 1))! \cdot (i + 1)\)即可
至于为什么这样会不重不漏、刚好删掉所有非法方案?
唯一的疑惑就在于有一些方案不在第一次非法时删除
但不难发现将第一段+第二段看成一个操作的话
每一个操作刚好不重不漏加上了所有的合法方案
代码
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 2000+9; const int MOD = 1000000007; int tot,n,_hash[N],arr[N],f[N],POW[N]; namespace Fenwick_Tree{ #define BIT Fenwick_Tree #define lowbit(x) ((x)&-(x)) int cnt[N][N]; inline void insert(int t, int p, int delta) { for (int i=p;i<=n;i+=lowbit(i)) (cnt[t][i] += delta) %= MOD; } inline int query(int t, int p) { int ret = 0; for (int i=p;i;i-=lowbit(i)) (ret += cnt[t][i]) %= MOD; return ret; } }; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ n = read(); for (int i=1;i<=n;i++) _hash[i] = arr[i] = read(); sort(_hash+1, _hash+1+n); tot = unique(_hash+1, _hash+1+n) - _hash - 1; for (int i=1;i<=n;i++) arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash; POW[1] = POW[0] = 1; for (int i=2;i<=n;i++) POW[i] = (LL)POW[i-1] * i % MOD; for (int i=1;i<=n;i++) { for (int j=n,tmp;j>1;j--) { tmp = BIT::query(j-1,arr[i]); (f[j] += tmp) %= MOD; BIT::insert(j,arr[i],tmp); } BIT::insert(1,arr[i],1); f[1]++; } int vout = 0; for (int i=1;i<=n;i++) { (vout += (LL)f[i] * POW[n-i] % MOD) %= MOD; if (i < n) (vout -= ((LL)f[i+1] * POW[n-i-1] % MOD) * (i+1) % MOD) %= MOD; } printf("%d\n",(vout+MOD)%MOD); return 0; }
I’ve been absent for some time, but now I remember why I used to love this site. Thanks , I will try and check back more often. How frequently you update your site?
I’ve been exploring for a little for any high-quality articles or blog posts on this kind of area . Exploring in Yahoo I at last stumbled upon this website. Reading this info So i am happy to convey that I’ve an incredibly good uncanny feeling I discovered just what I needed. I most certainly will make sure to do not forget this website and give it a look regularly.