QOJ7018 Insertion Sort
原题链接：Insertion Sort
分析
分讨的本质就是有问题的。如果继续容斥的话，那就完蛋了。
正确的式子就是：
a n s = k ! × ( 1 + C n − k 1 × C n − 1 1 ) ans=k!\times(1+C_{n-k}^{1}\times C_{n-1}^{1})ans=k!×(1+Cn−k1×Cn−11)
就是相当于前k kk的全排，后面的1 11是序列完全有序，后面的相当于在剩下的n − k n-kn−k里挑一个，然后插到剩下里面去，做完了。
所以，我真的想到了吗？可能吧，不过，确实少了一些东西吧……
下次最好先打一个表！！！
哦，我推出来……但是，我插板的时候按照n nn来算了😭
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intT;intn,k,p;signedmain(){// freopen("prefixsort.in", "r", stdin);// freopen("prefixsort.out", "w", stdout);cin>>T;for(intcs=1;cs<=T;cs++){cin>>n>>k>>p;k=min(n,k);intans=(1+(n-k)*(n-1)%p)%p;for(inti=2;i<=k;i++){ans=ans*i%p;}cout<<"Case #"<<cs<<": "<<ans%p<<'\n';}}CF115D Unambiguous Arithmetic Expression
原题链接：Unambiguous Arithmetic Expression
分析
和我想的也差不多吧，类似一个递归，就是说，你会发现，一坨符号会影响之后的一坨数。
也不全对。我场上看出来了……40 % 40\%40%？
就是说，一旦出现* /相连就完蛋了。然后，对于一段+ - * /，第一个是二元的，其他都是一元的……反正就是这个意思吧，你懂的。
就是* /不能做单元的运算符。
我们来设一个非常神奇的DP式子，我们设d p i , j dp_{i,j}dpi,j表示填完前i ii个字符后的括号，多出j jj个左括号的方案数。
？？？
换句话说不就是要消耗j jj个双元吗？
考虑一边完全可以兼顾另外一边，所以，非常完美。
那么，转移完全是容易的，直接：
d p i , j = ∑ k = j i d p i − 1 , k dp_{i,j}=\sum\limits_{k=j}^{i}{dp_{i-1,k}}dpi,j=k=j∑idpi−1,k
正解
#include<bits/stdc++.h>#defineintlonglong#definemod1000003usingnamespacestd;constintN=2005;string s;intdp[N][N];intn,a[N];signedmain(){freopen("expression.in","r",stdin);freopen("expression.out","w",stdout);cin>>s;intm=0;for(inti=0;i<(int)s.length();i++){if(s[i]=='*'||s[i]=='/'){a[++m]=1;}elseif(s[i]=='+'||s[i]=='-'){a[++m]=3;}elseif(s[i]>='0'&&s[i]<='9'){while(i+1<(int)s.length()&&s[i+1]>='0'&&s[i+1]<='9')i++;a[++m]=2;}}n=m;for(inti=1;i<=n;i++){if(a[i]==1&&a[i-1]!=2){cout<<0;return0;}}dp[0][0]=1;for(inti=1;i<=n;i++){if(a[i]!=2)for(intj=1;j<=n;j++){dp[i][j]=dp[i-1][j-1];}else{for(intj=n;j>=0;j--){dp[i][j]=(dp[i-1][j]+dp[i][j+1])%mod;}}}cout<<dp[n][0];}CF2183F Jumping Man
原题链接：Jumping Man
分析
哦，我是不是没看懂这题的题面？那不补了！
LGP17427 [ICPC 2018 Xuzhou R] Rikka with An Unnamed Temple
原题链接：[ICPC 2018 Xuzhou R] Rikka with An Unnamed Temple
分析
我的暴力，我的110 p t s 110pts110pts😭
我们来学一下这个图上的DP吧。
