Uva 12298 超级扑克2

题目链接：https://vjudge.net/problem/UVA-12298

题意：

1、超级扑克，每种花色有无数张牌，但是，这些牌都是合数；比如黑桃：4,6,8,9,10,,,,

2、现在拿走了一些牌；

3、从每种花色里面抽取一张牌，和为 n ,有多少种方案；

4、现在 和 n 是一个区间，a到b;

分析：

四种花色，每种取一张，有多少种方案？

和 为 n ,即 将4个多项式乘起来，指数为 n ，就得到了和为 N 的一种方案，那么方案种数就是他的系数；

将这些多项式相乘使用FFT

模板是lrj大神的；哈哈；

 #include <complex>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const long double PI = acos(0.0)*2.0;

 typedef complex<double> CD;

 // Cooley-Tukey的FFT算法，迭代实现。inverse = false时计算逆FFT

 inline void FFT(vector<CD> &a, bool inverse) {

     int n = a.size();

     // 原地快速bit reversal

     for(int i = , j = ; i < n; i++) {

         if(j > i) swap(a[i], a[j]);

         int k = n;

         while(j & (k >>= )) j &= ~k;

         j |= k;

     }

     double pi = inverse ? -PI : PI;

     for(int step = ; step < n; step <<= ) {

         // 把每相邻两个“step点DFT”通过一系列蝴蝶操作合并为一个“2*step点DFT”

         double alpha = pi / step;

         // 为求高效，我们并不是依次执行各个完整的DFT合并，而是枚举下标k

         // 对于一个下标k，执行所有DFT合并中该下标对应的蝴蝶操作，即通过E[k]和O[k]计算X[k]

         // 蝴蝶操作参考：http://en.wikipedia.org/wiki/Butterfly_diagram

         for(int k = ; k < step; k++) {

             // 计算omega^k. 这个方法效率低，但如果用每次乘omega的方法递推会有精度问题。

             // 有更快更精确的递推方法，为了清晰起见这里略去

             CD omegak = exp(CD(, alpha*k));

             for(int Ek = k; Ek < n; Ek += step << ) { // Ek是某次DFT合并中E[k]在原始序列中的下标

                 int Ok = Ek + step; // Ok是该DFT合并中O[k]在原始序列中的下标

                 CD t = omegak * a[Ok]; // 蝴蝶操作：x1 * omega^k

                 a[Ok] = a[Ek] - t;  // 蝴蝶操作：y1 = x0 - t

                 a[Ek] += t;         // 蝴蝶操作：y0 = x0 + t

             }

         }

     }

     if(inverse)

         for(int i = ; i < n; i++) a[i] /= n;

 }

 inline vector<double> operator * (const vector<double>& v1,const vector<double>& v2) {

     int s1 = v1.size(),s2=v2.size(),S=;

     while(S < s1 + s2) S <<= ;

     vector<CD> a(S,), b(S,); // 把FFT的输入长度补成2的幂，不小于v1和v2的长度之和

     for(int i = ; i < s1; i++) a[i] = v1[i];

     FFT(a, false);

     for(int i = ; i < s2; i++) b[i] = v2[i];

     FFT(b, false);

     for(int i = ; i < S; i++) a[i] *= b[i];

     FFT(a, true);

     vector<double> res(s1 + s2 - );

     for(int i = ; i < s1 + s2 - ; i++) res[i] = a[i].real(); // 虚部均为0

     return res;

 }

 const int maxn =  + ;

 int composite[maxn];

 void sieve(int n) {

     int m = (int)sqrt(n+0.5);

     memset(composite,,sizeof(composite));

     for(int i=; i<=m; i++) {

         if(!composite[i])

             for(int j=i*i; j<=n; j+=i)

                 composite[j] = ;

     }

 }

 const char* suites = "SHCD";

 int idx(char suit) {

     return strchr(suites,suit)-suites;

 }

 int lost[][maxn];  //4张花色是否丢了

 int main() {

     sieve();

     int a,b,c;

     while(scanf("%d%d%d",&a,&b,&c),a) {

         memset(lost,,sizeof(lost));

         for(int i=; i<c; i++) {

             int d;

             char s;

             scanf("%d%c",&d,&s);

             lost[idx(s)][d] = ;

         }

         vector<double> ans(,),poly;

         for(int s=; s<; s++) {

             poly.clear();

             poly.resize(b+,);

             for(int i=; i<=b; i++) //合数里面挑,并且没有被拿走

                 if(composite[i]&&!lost[s][i]) poly[i]=1.0;

             ans = ans*poly;

             //ans.resize(b+1);

         }

         for(int i=a; i<=b; i++)

             printf("%0.lf\n",fabs(ans[i]));

         puts("");

     }

     return ;

 }