2015年沈阳网赛 Jesus Is Here(DP中的计数问题)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5459

题目描述：给定一个递推得来的字符串，问字符串中不同cff之间的距离之和，

递推规则：

s1=c; s2=ff

sn=s[n-2]s[n-1];

可以观察到任意一个c都被两个ff包含，所以相当于求任意两个c之间的距离之和。

设s[n-2]为p1,p2,p3,,,,p[x],s[n-1]为q1,q2,q3,,,,q[y];

X和y分别为字符串中c的个数；设cnt_c[i]为第i个字符串中c的个数,

all[i]表示第i个字符串的长度，

那么合并之后字符串为p1,p2,p3,,,,p[cnt_c[i-2]],q1+all[i-2],q2+all[i-2],q3+all[i-2]+,,,,q[cnt_c[i-1]]+all[i-2]

设T[i]表示第i个字符串中任意两个c的距离和，

T[i]=T[i-1]+T[i-2]+F[i];

现在讨论F[i]，首先考虑q1与之前的组合，

q1+all[i-2]-p1,q1+all[i-2]-p2,q1+all[i-2]-p3,,,q1+all[i-2]-p[cnt_c[i-2]];

合并之后就为：( q1+all[i-2] )*cnt_c[i-2] - (p1+p2+p3,,,+p[cnt_c[i-2]]);

加上q2,q3,,,q[cnt_c[i-1]]之后，答案就为(q1+q2+q3+,,,q[cnt_c[i-1]])*cnt_c[i-2]

+ all[i-2]*cnt_c[i-2] *cnt_c[i-1] - (p1+p2+p3,,,+p[cnt_c[i-2]])*cnt_c[i-1];

设s[i]表示第i个字符串中不同c之间的距离之和，

T[i]=T[i-2] + T[i-1] + s[i-1]*cnt_c[i-2] + all[i-2]*cnt_c[i-2] *cnt_c[i-1] - s[i-2]*cnt_c[i-1];

如果答案是负数,第一可能是(a%MOD+MOD)%MOD,第二可能是long long写成int了

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cstring>

#include <iostream>

#define mod 530600414

#define MOD 530600414

#define maxn 201315

#define LL long long

using namespace std;

LL s[maxn],cnt_c[maxn],all[maxn],T[maxn];

//cnt_c代表字符串中有多少个c

//all代表字符串中有多少个字符

//s代表字符串中c位置的和

//T[i]=(cnt_c[i-2]*s[i-1] + cnt_c[i-1] * cnt_c[i-2] *all[i-2] -cnt_c[i-1]*s[i-2]);

void solve()

{

  // memset(T,0,sizeof(T));

   cnt_c[]=;  cnt_c[]=;

   all[]=;    all[]=;

   s[]=;      s[]=;

   T[]=;      T[]=;

   for(int i=;i<=;i++)

   {

       cnt_c[i]=(cnt_c[i-]+cnt_c[i-])%MOD;

       all[i]=(all[i-]+all[i-])%MOD;

       s[i]=( (s[i-]+s[i-])%MOD + (cnt_c[i-]*all[i-]) %MOD ) %MOD;

       int a1=( ( ((cnt_c[i-]*all[i-])%MOD - (s[i-] ) ) %MOD *cnt_c[i-])%MOD )%MOD;

       int b1=(cnt_c[i-] * s[i-] ) %MOD;

       T[i]=((T[i-]+ T[i-]%MOD +MOD)) %MOD;

       T[i]=( (T[i]+a1+b1)%MOD +MOD)%MOD;

   }

}

int main()

{

  // freopen("test.txt","r",stdin);

   int t,Case=;

   scanf("%d",&t);

   solve();

   while(t--)

   {

       int input;

       scanf("%d",&input);

       printf("Case #%d: %lld\n",++Case,T[input]);

   }

   return ;

}

巴特西

2015年沈阳网赛 Jesus Is Here(DP中的计数问题)

最新文章

热门文章