转来的题面:

首先这题显然补集转化，就是用全部方案减去不含任何质数的方案。

然后怎么做呢?

考虑m比较小，我们能大力把<=m的质数全都筛出来。

发现n很大，要么倍增要么快速幂......

发现p相当小，所以我们能在mod p的同余系下做啊。

一看到同余系下求方案数立刻想到卷积和生成函数......

假设我们有一个多项式f(x)，其中x^i的系数为a个数的序列mod p为i的方案数(a为我们引入的变量)。

同时我们有另一个多项式g(x),其中x^i的系数为b个数的序列mod p为i的方案数(b为我们引入的变量)。

那么，我们如果让f(x)和g(x)做卷积的话，新的多项式x^i的系数就是(a+b)个数的序列mod p为i的方案数的说。

这就是生成函数了。

回到这个题，我们先初始化多项式f(x)，令x^i的系数为为1个数mod p为i的方案数。

然后我们求出这个多项式的n次方，就是我们需要的答案了。

发现这道题的p很小，我们连FFT都不用，直接用一个多项式类暴力快速幂就行了。复杂度O(m+p^2logn)，跑的飞起。

话说为什么p才100啊，如果修改一下模数然后NTT的话，可以做到p为1e5级别，n为1e18级别的。

代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define debug cout 6 typedef long long int lli; 7 using namespace std; 8 const int maxn=1e2+1e1,maxl=2e7+1e2,lim=2e7; 9 const int mod=20170408;10 11 bool vis[maxl];12 int p,m;13 14 struct Poly {15     lli dat[maxn];16     Poly() {17         memset(dat,0,sizeof(dat));18     }19     lli& operator [] (const int &x) {20         return dat[x];21     }22     const lli& operator [] (const int &x) const {23         return dat[x];24     }25     friend Poly operator * (const Poly &a,const Poly &b) {26         Poly ret;27         for(int i=0;i
          
           >= 1 ) base = base * base;58     }59     return ret;60 }61 62 int main() {63     static int n;64     static lli ans;65     scanf("%d%d%d",&n,&m,&p) , sieve();66     init();67     full = fastpow(full,n) , oly = fastpow(oly,n);68     ans = ( full[0] - oly[0] + mod ) % mod;69     printf("%lld\n",ans);70     return 0;71 }