P6811 「MCOI-02」Build Battle 建筑大师

,

P6811 「MCOI-02」Build Battle 建筑大师

Description

一个序列 $n$，给定独立询问 $m_i$，序列为 $1,2,3,…,m_i,1,2,…,(n-1)\bmod m_i+1$

求本质不同的子序列数。$q$ 组询问。

$n,q\le 1\times 10^6$

1s 512MB

Solution

Step1

定义 $f_i$ 表示到 $i$ 的本质序列不同的个数。

枚举 $x$ 表示子序列下一个权值，为了避免重复，$nex_{i,x}$ 表示从 $i$ 开始，下一个权值为 $x$ 的点的位置。$f_{nex[i][x]}\Leftarrow f_i$。

复杂度 $O(n^2q)$

Step2

可以发现，这样丝毫没有用到这个序列的特殊性。

$i$ 可以从 $i-1,i-2,…,i-m$ 转移过来。前缀和优化。

复杂度 $O(nq)$

Step3

令 $s_i=\sum\limits_{j=1}^{i} f_j$

则 $s_i=s_{i-1}+f_i=2s_{i-1}-s_{i-m-1}$ 。我们要求的就是 $s_n$。

接下来是从题解贺来的小 trick。

考虑组合意义，相同于从 $1$ 开始，目前在位置 $i$ ，可以走一步让 $i+1$ 让阈值 $v=v*2$，也可以走到 $i+m+1$ 让阈值 $v=-v$。答案就是走到位置 $n$ 的阈值之和。

观察到和怎么走并没有关系，而和走的步数有关系。则枚举走 $m+1$ 步的次数。则答案为
$$
s_n=\sum\limits_{i=0}^{\frac{n}{m}} 2^{n-(m+1)i} \times (-1)^i\times \dbinom{n-(m+1)i+i}{i}
$$
每次枚举 $m$ ，暴力计算。复杂度是调和级数 $O(n\log n)$

Code

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 int long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=1e9+7;
int suf[maxn*2],isuf[maxn*2],n,q,Ans[maxn],pw[maxn*2];
inline void add(int &x,int y) {x=(x+y)%mod;}
inline int power(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ans;
}
inline int C(int x,int y) {return suf[x]*isuf[y]%mod*isuf[x-y]%mod;}
signed main(void){
	int i,m,j;
	read(n);read(q);
	suf[0]=1;pw[0]=1;
	for (i=1;i<=2*n;i++) pw[i]=pw[i-1]*2%mod,suf[i]=suf[i-1]*i%mod;
	isuf[2*n]=power(suf[2*n],mod-2);
	for (i=2*n;i>=1;i--) isuf[i-1]=isuf[i]*i%mod;
	for (j=1;j<=n;j++) {
		int m=j+1;
		for (i=0;i<=n/m;i++) {
			if (i&1) add(Ans[j],mod-pw[n-m*i]*C(n-m*i+i,i)%mod);
			else add(Ans[j],pw[n-m*i]*C(n-m*i+i,i));
		}
	} 
	while (q--) {
		read(m);
		printf("%lld\n",Ans[min(n,m)]);
	}
	return 0;
}