Counting Sequences I（2019上海网络赛D）（暴力dfs or 打表）

Counting Sequences I

拿着OEIS上的一个类似的序列（当时以为是相同的）怼了半天。。。欲哭无泪

题意：问有多少长度为 $n$n的正整数序列满足它们的和等于它们的积（每一位置对应相同认为是同一序列）

思路：没啥思路，暴力即可

1. 首先，序列中不等于 $1$1的值不能太多，比如 $2^{12}$212等于4096，显然乘积增长太快了！因此大多数序列都会被剪枝掉，保证了时间复杂度很低
2. 枚举的过程按从大到小的方式进行枚举，在每个位置都检验一遍是否后面所有数字都取 $1$1是刚好合理的
3. 若合理，则直接使用 $n!\ast {\displaystyle \sum ^{取的相同数}inv\left(i\right)}$n!∗∑取的相同数​inv(i) 计算出这些数字能产生的合法序列数

题面描述

恰好卡过去的暴力代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int a[30];
ll f[maxn], inv[maxn];

ll dfs(int n, int cur, int pre, int l, int r) {
	if(l+n+1-cur==r) {
		ll ans=f[n], now=1;
		for(int i=2; i<cur; ++i)
			if(a[i]==a[i-1]) now++;
			else ans=ans*inv[now]%mod, now=1;
		if(cur>1&&a[cur-1]!=1) ans=ans*inv[now]%mod*inv[n+1-cur]%mod;
		else ans=ans*inv[now+n+1-cur]%mod;
		return ans;
	}
	if(cur>n||pre==1) return 0;
	ll ans=0;
	for(int i=min(n,pre); i>=1; --i)
		if(l+i+n-cur>=r*i) a[cur]=i, ans=(ans+dfs(n,cur+1,i,l+i,r*i))%mod;
	return ans;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
	f[0]=1; for(int i=1; i<=3000; ++i) f[i]=i*f[i-1]%mod;
	inv[0]=inv[1]=1;
	for(int i=2; i<=3000; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2; i<=3000; ++i) inv[i]=inv[i]*inv[i-1]%mod;
    int T=read();
	while(T--) printf("%lld\n", dfs(read(),1,inf,0,1));
}