We can know that the length of $S_{i}$ would not exceed number of $x_{j}$, such that $x_{j}\leq x_{i}$
If we sort the numbers in increasing order, all $S_{i}$ would reach the maximum length!
So we can calculate the first answer according to descriptions above.
For the second answer, we know that for each $S_{i}$, all values $<x_{i}$ on the left of $x_{i}$ must form a non-increasing sequence, all values$<x_{i}$ on the right of $x_{i}$ must form a non-decreasing sequence, or $S_{i}$ would not be able to reach the maximum length.
So the optimal permutations are composed of a non-increasing sequence and a non-decreasing sequence.
Let's sort the pairs: $\{(v_{k},f_{k})\}$
The number of such optimal permutations is $\prod_{i=1}^{P-1} (f_{i}+1)$
If you don't know why, let's call the location of maximum values $peak$.
for every $v_{k}$, we have $f_{k}$ of such numbers, we can decide to put $0,1,2,...,f_{k}$ on the left of $peak$ and $f_{k},f_{k}-1,f_{k}-2,...,0$ on the right of $peak$, so there are $f_{k}+1$ ways to assign values of $v_{k}$. Therefore, you know, the number of ways to assign all $v_{k}$ is $\prod_{i=1}^{P-1} (f_{i}+1)$. :)
Total time complexity: $O(P\log P)$
Note:
1. The first answer is no need to modulo $10^{9}+7$.
2. The first answer must be handled with unsigned long long, not long long.
code:
#include<cstdio> #include<algorithm> using namespace std; typedef unsigned long long LL; const LL MOD=1000000007LL; //LL LEVEL[100001]; int N; vector<pair<int,LL> >S; LL Solve1() { LL ans=0LL,sum=0LL; for(const auto &p:S) { sum+=p.second;//)%=MOD; ans+=sum*p.second;//)%=MOD; } return ans; } int main() { // LEVEL[0]=1LL; // for(int i=1;i<=100000;i++)LEVEL[i]=(LEVEL[i-1]*i)%MOD; // freopen("in.txt","r",stdin); int testcount;scanf("%d",&testcount); while(testcount--) { scanf("%d",&N); S.clear(); for(int i=0,v,f;i<N;i++)scanf("%d%d",&v,&f),S.push_back(make_pair(v,(LL)f)); sort(S.begin(),S.end()); const LL ans1=Solve1(); LL ans2=1LL; // for(const auto &p:S)(ans2*=LEVEL[p.second])%=MOD; S.pop_back(); for(const auto &p:S)(ans2*=p.second+1LL)%=MOD; static int kase=1; printf("Case %d: %llu %llu\n",kase++,ans1,ans2); } return 0; }
沒有留言:
張貼留言
歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原
注意:只有此網誌的成員可以留言。