Counting Sequences I

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

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

思路:没啥思路,暴力即可

  1. 首先,序列中不等于 1 1 1的值不能太多,比如 2 12 2^{12} 212等于4096,显然乘积增长太快了!因此大多数序列都会被剪枝掉,保证了时间复杂度很低
  2. 枚举的过程按从大到小的方式进行枚举,在每个位置都检验一遍是否后面所有数字都取 1 1 1是刚好合理的
  3. 若合理,则直接使用 n ! <mstyle displaystyle="true" scriptlevel="0"> <mover> </mover> i n v ( i ) </mstyle> n!*\displaystyle\sum^{取的相同数} inv(i) 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));
}