[CQOI2017]老C的键盘

题目描述

额，网上题解好像都是用的一大堆组合数，然而我懒得推公式。

设\(f[i][j]\)表示以\(i\)为根，且\(i\)的权值为\(j\)的方案数。

转移：

\[f[i][j]=\sum f[sn_1][k]*f[sn_2][q]
\]

需要判断一下\(k,q\)与\(j\)的关系满不满足题意就行了。

但是这样的答案显然不对，因为有些权值可能多次出现。

换句话说，有些权值可能没有出现。所以我们就用那个经典的容斥，枚举颜色数上界。

设\(g[s]\)表示颜色数最多为\(s\)的方案数，则\(\displaystyle ans=\sum_{s=1}^n (-1)^{n-s}C_n^sg[s]\)。

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 105

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=1e9+7;

int n;

char s[N];

int f[N][N];

int c[N][N];

int Mod(int a) {return a<0?a+mod:(a<mod?a:a-mod);}

int g[N][2];

int ans;

void update(int v,int sn,int flag,int sum) {

	if(s[sn]=='<') {

		for(int j=1;j<=sum;j++) g[j][flag]=Mod(g[j-1][flag]+f[sn][j-1]);

	} else {

		for(int j=sum;j>=1;j--) g[j][flag]=Mod(g[j+1][flag]+f[sn][j+1]);

	}

}

int work(int sum) {

	memset(f,0,sizeof(f));

	for(int i=n;i>=1;i--) {

		memset(g,0,sizeof(g));

		if(i*2<=n) update(i,i<<1,0,sum);

		else for(int j=1;j<=sum;j++) g[j][0]=1;

		if(i*2+1<=n) update(i,i<<1|1,1,sum);

		else for(int j=1;j<=sum;j++) g[j][1]=1;

		for(int j=1;j<=sum;j++) f[i][j]=1ll*g[j][0]*g[j][1]%mod;

	}

	int ans=0;

	for(int i=1;i<=sum;i++) ans=Mod(ans+f[1][i]);

	return ans;

}

int main() {

	n=Get();

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

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

			c[i][j]=(!j||i==j)?1:Mod(c[i-1][j-1]+c[i-1][j]);

	scanf("%s",s+2);

	int flag=1;

	for(int i=n;i>=1;i--,flag*=-1) {

		ans=(ans+flag*1ll*c[n][i]*work(i)%mod+mod)%mod;

	}

	cout<<ans;

	return 0;

}