【日常小测】count

  • 本文为博主原创，未经许可不得转载

首先朴素的dp式非常简单：$f[i]=\sum f[j]\times (i-j)^2$

然后考虑优化

首先看一下转移一步的情况：

$f[i+1]=\sum f[j]\times (i+1-j)^2$

$f[i+1]\sum f[j]\times (i-j)^2+2\sum f[j]\times (i-j)+\sum f[j]+f[i]$

所以我们维护向量$[\sum f[j],\sum f[j]\times (i-j),\sum f[j]\times (i-j)^2]$

然后分步转移即可

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
using namespace std;
const int mod=1e9+7;
int n,m,a[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
struct node{
	int a[4][4];
	node(){memset(a,0,sizeof(a));}
	inline node operator* (const node &b){
		node c;  memset(c.a,0,sizeof(c.a));
		for(int i=1;i<=3;++i)
			for(int j=1;j<=3;++j)
				for(int k=1;k<=3;++k)
					c.a[i][j]=add(c.a[i][j],mul(a[i][k],b.a[k][j]));
		return c;
	}
}zhuan[2],ans;
inline node fast(node a,int b){
	node ret; for(int i=1;i<=3;++i) ret.a[i][i]=1;
	for(;b;b>>=1,a=a*a)if(b&1) ret=ret*a;
	return ret;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();
	for(int i=1;i<=m;++i) a[i]=read();  a[++m]=n;
	zhuan[0].a[1][1]=1;  zhuan[0].a[1][2]=0;  zhuan[0].a[1][3]=1;
	zhuan[0].a[2][1]=1;  zhuan[0].a[2][2]=1;  zhuan[0].a[2][3]=1;
	zhuan[0].a[3][1]=1;  zhuan[0].a[3][2]=2;  zhuan[0].a[3][3]=2;
	zhuan[1].a[1][1]=1;  zhuan[1].a[1][2]=0;  zhuan[1].a[1][3]=0;
	zhuan[1].a[2][1]=1;  zhuan[1].a[2][2]=1;  zhuan[1].a[2][3]=0;
	zhuan[1].a[3][1]=1;  zhuan[1].a[3][2]=2;  zhuan[1].a[3][3]=1;
	ans.a[1][1]=1;  ans.a[2][1]=1;  ans.a[3][1]=1;  int now=0;
	for(int i=1;i<=m;++i){
		ans=fast(zhuan[0],a[i]-now-1)*ans;
		if(i!=m) ans=zhuan[1]*ans;
		now=a[i];
	}
	printf("%d\n",ans.a[3][1]);
	return 0;
}

本文标题:【日常小测】count

文章作者:chty

发布时间:2017年06月27日 - 21时12分

最后更新:2018年07月25日 - 21时31分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,