[这个Blog需要恢复] 568B
我决定以一个Codeforces的题目来恢复我的Blog更新
以后还会有题目,也许也还会有碎碎念
我发现
也许写碎碎念就是一种很好的方案
至少
不会感觉有多难受吧
因为难受的东西写出来
就不再难受了么
嗯,先不写那么多碎碎念了吧
另外
从现在起
我决定自己尝试翻译题目
题意:
给一个数n
求有n个元素的情况下
求有多少个关系的规则(a-->b)
使得不满足:
自反(a-->a)
但要求满足
对称(a-->b : b-->a)
结合(a-->b/b-->c : a-->c)
Sample 2:
n=2
3种:
空规则
单规则1-->1
单规则2-->2
双dp
dp表示答案,dp2表示满足对称和结合但不一定满足自反的答案
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include<set>#include<map>#include<list>#include<queue>#include<stack>#include<string>#include<math.h>#include<time.h>#include<vector>#include<bitset>#include<memory>#include<utility>#include<fstream>#include<stdio.h>#include<sstream>#include<iostream>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;int dp[4005];int dp2[4005];int c[4005][4005];const int modo=1000000007;int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; scanf("%d",&n); int i; for (i=0;i<=n;i++) { int j; c[i][0]=1; for (j=1;j<=i;j++) { c[i][j]=c[i-1][j-1]+c[i-1][j]; c[i][j]%=modo; } } dp[0]=0; dp2[0]=1; for (i=1;i<=n;i++) { int j; for (j=1;j<n;j++) { dp[i]=(dp[i]+(long long)dp[j]*c[i-1][i-j-1])%modo; dp2[i]=(dp2[i]+(long long)dp2[j]*c[i-1][i-j-1])%modo; } dp2[i]+=dp2[i-1]; dp2[i]++; dp2[i]%=modo; dp[i]+=dp2[i-1]; dp[i]%=modo; //printf("dp[%d] = %d dp2[%d] = %d\n",i,dp[i],i,dp2[i]); } printf("%d\n",dp[n]); return 0;}<span style="white-space: normal;"></span> |
评论 (0)