我决定以一个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表示满足对称和结合但不一定满足自反的答案

代码:

#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;
}