【ZJOI2011】细胞

Source and Judge

ZJOI2011
bzoj2323

Record

2h

Analysis

请先思考后再展开

这题的两部分显然是分开的
然后我就一直在想构造一个方案被重复计数的情况,然后发现构造不出来,但总觉得一定是存在的……样例太水所以没体现,恩一定是这样的
想半天膜题解看到第一句话就自闭了,怎么你们都有这么好的直觉woc

总之我们只需要考虑分割方案带来的长度就好了,不需要考虑质量
知道长度就好办了,不难发现是个fib
$\sum fib[(\sum b_i)-1]=\frac{fib[1]}{A^2} \sum( \prod A^{b_i} )$
$F_i=\sum F_j \times A^{num(j+1,i)}$
然后注意一下矩阵的交换律即可
$ans=F_n \times \frac{fib[1]}{A^2}$
右边那个考虑一下A的实际意义,手推一下即可

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
const int MOD=1e9+7;
void add(ll &x,ll y) {x+=y;if(x>=MOD) x-=MOD;}
struct Matrix
{
ll a[2][2];
Matrix(){memset(a,0,sizeof a);}
friend Matrix operator +(Matrix x,Matrix y)
{
for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) add(x.a[i][j],y.a[i][j]);
return x;
}
friend Matrix operator *(Matrix x,Matrix y)
{
Matrix t;
for(int i=0;i<=1;i++) for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++) add(t.a[i][j],x.a[i][k]*y.a[k][j]%MOD);
return t;
}
};
const int MAX_N=1100;
char s[MAX_N];
Matrix pre[MAX_N][MAX_N],f[MAX_N],A;
Matrix pre2[MAX_N][20];
void main()
{
A.a[0][1]=A.a[1][0]=A.a[1][1]=1;
pre2[0][1]=A;for(int j=2;j<=10;j++) pre2[0][j]=pre2[0][j-1]*pre2[0][1];
for(int i=1;i<MAX_N;i++)
{
pre2[i][1]=pre2[i-1][10];
for(int j=2;j<=10;j++) pre2[i][j]=pre2[i][j-1]*pre2[i][1];
}
int n;scanf("%d%s",&n,s+1);
for(int r=1;r<=n;r++)
{
pre[r][r]=pre2[0][s[r]-'0'];
for(int l=r-1;l>=1;l--) pre[l][r]=pre[l+1][r]*pre2[r-l][s[l]-'0'];
}
f[0].a[0][0]=f[0].a[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
f[i]=f[i]+pre[j+1][i]*f[j];
Matrix tmp;tmp.a[0][0]=-1;tmp.a[1][0]=1;
printf("%lld",((f[n]*tmp).a[1][0]+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6e7f.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%