首页 > 代码库 > HDU5322 Hope
HDU5322 Hope
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 420 Accepted Submission(s): 227
Problem Description
Hope is a good thing, which can help you conquer obstacles in your life, just keep fighting, and solve the problem below.
In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters.
There is a permutation A1,A2,...An, now we define its value as below:
For each Ai, if there exists a minimum j satisfies j>i and Aj>Ai , then connect an edge between Ai and Aj , so after we connect all the edges, there is a graph G, calculate the product of the number of nodes in each component as an integer P. The permutation value is P * P.Now, Mr. Zstu wants to know the sum of all the permutation value of n. In case the answer is very big, please output the answer mod 998244353.
Just in case some of you can’t understand, all the permutations of 3 are
1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1
In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters.
There is a permutation A1,A2,...An, now we define its value as below:
For each Ai, if there exists a minimum j satisfies j>i and Aj>Ai , then connect an edge between Ai and Aj , so after we connect all the edges, there is a graph G, calculate the product of the number of nodes in each component as an integer P. The permutation value is P * P.Now, Mr. Zstu wants to know the sum of all the permutation value of n. In case the answer is very big, please output the answer mod 998244353.
Just in case some of you can’t understand, all the permutations of 3 are
1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1
Input
There are multiple test cases.
There are no more than 10000 test cases.
Each test case is an integer n(1≤n≤100000).
There are no more than 10000 test cases.
Each test case is an integer n(1≤n≤100000).
Output
For each test case, output the answer as described above.
Sample Input
12
Sample Output
15
Author
ZSTU
Source
2015 Multi-University Training Contest 3
Recommend
wange2014
给出一个排列，每个点向它右面离它最近的且比它大的点连无向边，每个连通块的价值为这个连通块大小的平方，每个排列的价值为所有连通块价值之积。求n个数的所有排列的价值之和。
动态规划 花式递推/NTT加速
考虑到放完前i个数再放i+1，不管i+1放在哪里，i+1之前的数形成了一个连通块，且对之后的没有影响。
设f[i]表示一个大小为i的连通块，枚举其中最大的那个数的位置在第j个，得到方程：
$ f[i]=\sum_{j=1}^{i} f[i-j] * j^2 * C(i-1,j-1)*(j-1)! $
最大的数在第j个位置时，j和它前面的所有数构成一个连通块，方案有$ C(i-1,j-1)*(j-1)! $种，贡献为j^2，j后面的连通块贡献为f[i-1]
此时复杂度为$O(n^2)$
接下来可以用数学方法花式递推，或者用分治NTT加速运算
数学：
(留坑待填)
很优美对吧？
但这是一道NTT的练习题呀
不用NTT的话就没有意义！
NTT
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mod=998244353;10 const int G=3;11 const int mxn=100010;12 int read(){13 int x=0,f=1;char ch=getchar();14 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}15 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}16 return x*f;17 }18 LL inv[mxn],fac[mxn];19 void init(){20 inv[0]=inv[1]=1;21 fac[0]=fac[1]=1;22 for(int i=2;i<mxn;i++){23 fac[i]=fac[i-1]*i%mod;24 inv[i]=((-mod/i)*inv[mod%i]%mod+mod)%mod;25 }26 for(int i=2;i<mxn;i++)inv[i]=inv[i-1]*inv[i]%mod;27 return;28 }29 LL ksm(LL a,LL k){30 LL res=1;31 while(k){32 if(k&1)res=res*a%mod;33 a=a*a%mod;34 k>>=1;35 }36 return res;37 }38 int N,len,rev[mxn<<1];39 LL a[mxn<<1],b[mxn<<1];40 LL f[mxn];41 void NTT(LL *a,int flag){42 for(int i=0;i<N;i++)if(i<rev[i])swap(a[i],a[rev[i]]);43 for(int i=1;i<N;i<<=1){44 int p=i<<1;45 LL gn=ksm(G,(flag==1)?(mod-1)/p:(mod-1)-(mod-1)/p);46 for(int j=0;j<N;j+=p){47 LL g=1;48 for(int k=0;k<i;k++,g=g*gn%mod){49 LL x=a[j+k],y=g*a[j+k+i]%mod;50 a[j+k]=(x+y)%mod;51 a[j+k+i]=(x-y+mod)%mod;52 }53 }54 }55 if(flag==-1){56 LL INV=ksm(N,mod-2);57 for(int i=0;i<N;i++)a[i]=a[i]*INV%mod;58 }59 return;60 }61 void solve(int l,int r){62 if(l==r){63 f[l]=(f[l]+(LL)l*l%mod)*fac[l-1]%mod;64 return;65 }66 int i,j,mid=(l+r)>>1;67 solve(l,mid);68 int m=(mid-l+1)<<1;69 for(N=1,len=0;N<=m;N<<=1)len++;70 for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));71 for(i=0;i<N;i++)a[i]=b[i]=0;72 for(i=l;i<=mid;i++)73 a[i-l]=f[i]*inv[i]%mod; 74 for(i=l;i<=r;i++)75 b[i-l]=(LL)(i-l)*(i-l)%mod;76 NTT(a,1);NTT(b,1);77 for(i=0;i<N;i++)a[i]=a[i]*b[i]%mod;78 NTT(a,-1);79 for(i=mid+1;i<=r;i++){80 (f[i]+=a[i-l])%=mod;81 }82 solve(mid+1,r);83 return;84 }85 int main(){86 int i,j,x;87 init();88 f[0]=1;89 solve(0,100000);90 while(scanf("%d",&x)!=EOF){91 printf("%lld\n",f[x]);92 }93 return 0;94 }
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 420 Accepted Submission(s): 227
Problem Description
Hope is a good thing, which can help you conquer obstacles in your life, just keep fighting, and solve the problem below.
In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters.
There is a permutation A1,A2,...An, now we define its value as below:
For each Ai, if there exists a minimum j satisfies j>i and Aj>Ai , then connect an edge between Ai and Aj , so after we connect all the edges, there is a graph G, calculate the product of the number of nodes in each component as an integer P. The permutation value is P * P.Now, Mr. Zstu wants to know the sum of all the permutation value of n. In case the answer is very big, please output the answer mod 998244353.
Just in case some of you can’t understand, all the permutations of 3 are
1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1
In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters.
There is a permutation A1,A2,...An, now we define its value as below:
For each Ai, if there exists a minimum j satisfies j>i and Aj>Ai , then connect an edge between Ai and Aj , so after we connect all the edges, there is a graph G, calculate the product of the number of nodes in each component as an integer P. The permutation value is P * P.Now, Mr. Zstu wants to know the sum of all the permutation value of n. In case the answer is very big, please output the answer mod 998244353.
Just in case some of you can’t understand, all the permutations of 3 are
1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1
Input
There are multiple test cases.
There are no more than 10000 test cases.
Each test case is an integer n(1≤n≤100000).
There are no more than 10000 test cases.
Each test case is an integer n(1≤n≤100000).
Output
For each test case, output the answer as described above.
Sample Input
12
Sample Output
15
Author
ZSTU
Source
2015 Multi-University Training Contest 3
Recommend
wange2014
HDU5322 Hope
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。