模拟赛的题

好神仙啊

---

之前的Solution很蠢 现在已经update....

---

题意

有$ n$个商品价格均为$ 1$,您有$ m$种面值的货币，面值为$ C_1..C_m$

每种物品你有$ P$的概率选取，然后你需要选出若干货币购买这些物品

购买商品不存在找零，求浪费在找零上的钱的期望对$ 1e9+7$取模

$ n \leq 10^9 \ m \leq 10^2 \ C_iC_j \leq 10^4$

---

$Solution $

垃圾模数毁我青春

首先考虑$ m=1$怎么做

枚举购买的物品$ a$

概率为$ P(a)=\binom{n}{a}p^a(1-p)^{n-a}$

显然浪费的钱数$ W(a)$可以$ O(1)$计算

然后发现$ W(a)=W(a \bmod C_1)$，即我们只关心选出物品的数量模$ C_1$意义下的每个值的概率

在模意义下建生成函数

即我们要求的多项式为$(px+1-p)^n $长度为$ C_1$的循环卷积结果

注意这里是循环卷积

暴力卷积的时间复杂度是$ O(10^8·\log n)$

一开始看到时限8s就开开心心的去写了，写完一交爆零看到10组数据，然后看到模数就扔题吃饭去了...

使用拆系数$ FFT$/三模数$ NTT$优化这个卷积即可

时间复杂度$ O(10^4·\log 10^4·\log n)$

 

然后考虑$ m>1$怎么做

其实吃饭的时候嘴巴bb出来了...吃完饭回机房比赛已经结束了...

反正本来也不可能写得出来的...

首先求$ v=\gcd(C_1,C_2..C_m)$，

根据$ NOIP2017$小凯的疑惑，最大的不能被货币表示出的面值$ kv$应该不超过最大的一对$ C$的乘积

这里好像很感性啊..求评论区给出证明QwQ

因此我们对于选出物品数量不超过$ 10^4$的特殊处理

即对于$ i \leq 10^4$求出恰好选了$ i$个物品的概率$ \binom{n}{i}·p^i·(1-p)^{1-i}$

写了个$ MTT$跑的还挺快...

不过常数依然大就是了...

---

$ my \ code$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define block 32768#define p 1000000007#define rt register int#define ll long longusing namespace std;inline ll read(){ ll x=0;char zf=1;char ch=getchar(); while(ch!='-'&&!isdigit(ch))ch=getchar(); if(ch=='-')zf=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int k,m,n,x,y,z,cnt,ans,v;namespace any_module_NTT{ vector
             
              R; const double PI=acos(-1.0); struct cp{ double x,y; cp operator +(const cp s)const{ return {x+s.x,y+s.y};} cp operator -(const cp s)const{ return {x-s.x,y-s.y};} cp operator *(const cp s)const{ return {x*s.x-y*s.y,x*s.y+y*s.x};} }w[16][32768]; void FFT(const int n,vector
              
               &A){ A.resize(n); for(rt i=0;i
               
                R[i])swap(A[i],A[R[i]]); for(rt i=1,s=0;i
                
                 <<=1,s++){ for(rt j=0;j
                 
                  <<1){ for(rt k=0;k
                  

Mul(vector

&x,vector

&y){ int sz=x.size()+y.size()-1,lim=1; while(lim<=sz)lim<<=1;R.resize(lim); vector

AB(lim),CD(lim),AC(lim),BC(lim); for(rt i=1;i

>1]>>1)|(i&1)*(lim>>1); for(rt i=0;i

>15; for(rt i=0;i

>15; FFT(lim,AB);FFT(lim,CD); for(rt i=0;i