loj#6132. 「2017 山东三轮集训 Day1」Flair
题解
5 分钟 read (About 722 words)

loj#6132. 「2017 山东三轮集训 Day1」Flair

原题传送门：>Here<

做过家喻户晓的小凯的疑惑的人应该会熟悉一个性质，即两种互质钱币最大不能表示的数为$ab-a-b​$。

而我们发现一个非常好的性质：$c_ic_j\le 10000(i\ne j)$

设$v=gcd(c_1,c_2,\cdots,c_m)$，则所有$\ge 10000$的$v​$的倍数都可以被表示。

这时我们只需要考虑选出的菜的数量$\%v=i​$的方案数。

设$f=(100-p)+px$，我们对这个多项式做循环卷积，得到$f^n$，$f^n_i$表示的就是在$n$道菜中随机选，选出菜的数量$\%v=i​$的方案数。

这样答案就是$\sum_{i=1}^{v-1}f^n_i(v-i)$

我们发现上式假设了$n$以内所有$v$的倍数都是可以被表示的，所以可以这样做。

但是我们知道$10000$以内有一些位置不能被表示，所以它们需要特殊处理。

对于一个数$i$，我们在之前统计答案的时候假定比它大的第一个能被表示的数为$v\lfloor {i \over v}\rfloor$，假设实际上是$price_i$（可以背包得到），那么答案需要加上$(price_i-v\lfloor {i \over v}\rfloor)p^i(100-p)^{n-i}\binom{n}{i}$，其中$p^i(100-p)^{n-i}\binom{n}{i}$是选出$i$道菜的可能性。

这样基本就完事了，但是这道题的模数很恶心，是$10^9+7$，所以需要使用$MTT$（在线学习.jpg）

代码：

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <cmath>

using std::swap;
typedef long long ll;

long double pi=3.1415926535897932384626433;
struct cp{
	long double x,y;
	inline cp operator+(const cp &a)const{return (cp){x+a.x,y+a.y};}
	inline cp operator-(const cp &a)const{return (cp){x-a.x,y-a.y};}
	inline cp operator*(const cp &a)const{return (cp){x*a.x-y*a.y,x*a.y+y*a.x};}
}a[200001],b[200001],c[200001],d[200001],w[18][1<<17];
int P=1000000007,Lim,L,v,R[200001];
inline void check(int &a){if(a>=P)a-=P;}
const cp v1=(cp){0.5,0},v2=(cp){0,-0.5},v3=(cp){0,1};
void FFT(cp *a){
	for(int i=0;i<Lim;++i)if(i<R[i])swap(a[i],a[R[i]]);
	for(int i=1,lg=0;i<Lim;i<<=1,++lg)
		for(int j=0;j<Lim;j+=(i<<1))
			for(int k=0;k<i;++k){
				const cp Nx=a[j+k],Ny=a[i+j+k]*w[lg][k];
				a[j+k]=Nx+Ny;
				a[i+j+k]=Nx-Ny;
			}
}
void MTT(int *F,int *G,int *ans,int len){
	Lim=1,L=-1;
	while(Lim<len)Lim<<=1,++L;
	for(register int i=0;i<Lim;++i)	R[i]=(R[i>>1]>>1)|((i&1)<<L),
									a[i].x=F[i]&32767,a[i].y=F[i]>>15,
									c[i].x=G[i]&32767,c[i].y=G[i]>>15;
	FFT(a);
	if(F!=G)FFT(c);
	else memcpy(c,a,sizeof a);
	for(register int i=0;i<Lim;++i){
		static cp na,nb,nc,nd;
		const int pl=(Lim-1)&(Lim-i);
		na=(a[i]+(cp){a[pl].x,-a[pl].y})*v1;
		nb=(a[i]-(cp){a[pl].x,-a[pl].y})*v2;
		nc=(c[i]+(cp){c[pl].x,-c[pl].y})*v1;
		nd=(c[i]-(cp){c[pl].x,-c[pl].y})*v2;
		b[pl]=na*nc+na*nd*v3;
		d[pl]=nb*nc+nb*nd*v3;
	}
	FFT(b),FFT(d);
	memset(ans,0,Lim<<2);
	for(register int i=0;i<Lim;++i){
		static long long t1,t2,t3;
		t1=(b[i].x/Lim)+0.5,t2=(b[i].y/Lim)+(d[i].x/Lim)+0.5,t3=(d[i].y/Lim)+0.5;
		check(ans[i%v]+=((((t3%P)<<30)+((t2%P)<<15)+t1)%P));
	}
}
void qsm(int *a,int b,int *ans){
	memset(ans,0,Lim<<2);
	ans[0]=1;
	int lena=(v!=1)+1,lenb=1;
	while(b){
//		for(int i=0;i<Lim;i++)printf("%d ",a[i]);putchar('\n');
//		for(int i=0;i<Lim;i++)printf("%d ",ans[i]);putchar('\n');
		if(b&1)MTT(ans,a,ans,lena+lenb-1),lenb=lena+lenb-1;
		MTT(a,a,a,(lena<<1)-1),lena=(lena<<1)-1;
		if(lena>v)lena=v;
		if(lenb>v)lenb=v;
		b>>=1;
	}
}
int T,ans,C,cnt;
int ans1[200001],tem[200001],price[20001],inv[20001],n,m,p,power[20001][2];
bool vis[10001];
int ksm(int a,int b){
	static int ans,it;
	ans=1,it=0;
	while(b){
		if(b&1)ans=(ll)ans*power[it][a]%P;
		b>>=1;
		++it;
	}
	return ans;
}
int read(){
	static int x;
	x=0;
	static char ch;
	ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
int main(){
	T=read();
	for(int i=0,tem=1;i<18;++i,tem<<=1){
		for(int j=0;j<tem;++j)
			w[i][j]=(cp){cos(pi*j/tem),sin(pi*j/tem)};
	}
	inv[0]=inv[1]=1;
	for(int i=2;i<=10000;++i)inv[i]=(ll)inv[P%i]*(P-P/i)%P;
	while(T--){
		n=read(),m=read(),p=read();
		if(m==1){
			v=read();
			memset(tem,0,Lim<<2);
			tem[1%v]=p,tem[0]+=(100-p);
			qsm(tem,n,ans1);
			ans=0;
			for(int i=1;i<v;++i)check(ans+=(ll)ans1[i]*(v-i)%P);
			printf("%d\n",ans);
			continue;
		}
		memset(vis,0,sizeof vis);
		vis[0]=1;v=0;
		for(int i=1,x;i<=m;++i){
			x=read();
			v=std::__gcd(v,x);
//			printf("%d\n",x);
			for(int j=x;j<=10000;++j)vis[j]|=vis[j-x];
//			for(int j=1;j<=n;j++)printf("%d ",(int)vis[j]);putchar('\n');
		}
		memset(tem,0,Lim<<2);
		tem[1%v]=p,tem[0]+=(100-p);
		qsm(tem,n,ans1);
//		for(int i=0;i<v;i++)printf("%d ",ans1[i]);putchar('\n');
//		for(int i=1;i<=n;i++)printf("%d ",(int)vis[i]);putchar('\n');
		ans=0;
		for(int i=1;i<v;++i)check(ans+=(ll)ans1[i]*(v-i)%P);
		for(int i=10000;i;--i)price[i]=vis[i]?0:(price[i+1]+1);
//		for(int i=1;i<=n;i++)printf("%d ",price[i]);putchar('\n');
		cnt=(10000/v)-1,C=n;
		if(cnt>n)cnt=n;
		power[0][0]=p;
		power[0][1]=100-p;
		for(int i=1;i<=30;++i)power[i][0]=(ll)power[i-1][0]*power[i-1][0]%P,power[i][1]=(ll)power[i-1][1]*power[i-1][1]%P;
		for(int i=1;i<=cnt;++i){
			const int cost=price[i]-((i%v==0)?0:(v-i%v));
//			printf("%d %d %d %d\n",C,ksm(p,i),ksm(100-p,n-i),cost);
			check(ans+=1ll*C*ksm(0,i)%P*ksm(1,n-i)%P*cost%P);
			C=1ll*C*(n-i)%P*inv[i+1]%P;
		}
		printf("%d\n",ans);
	}
}
# DP, MTT
luoguP5072 [Ynoi2015]盼君勿忘
0112模拟赛 吃干饭

Comments

Follow

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×