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大神的；哈哈；

  1 #include <complex>
  2 #include <cmath>
  3 #include <vector>
  4 #include <cstring>
  5 #include <cstdio>
  6 
  7 using namespace std;
  8 
  9 const long double PI = acos(0.0)*2.0;
 10 typedef complex<double> CD;
 11 
 12 
 13 // Cooley-Tukey的FFT算法，迭代实现。inverse = false时计算逆FFT
 14 inline void FFT(vector<CD> &a, bool inverse) {
 15     int n = a.size();
 16     // 原地快速bit reversal
 17     for(int i = 0, j = 0; i < n; i++) {
 18         if(j > i) swap(a[i], a[j]);
 19         int k = n;
 20         while(j & (k >>= 1)) j &= ~k;
 21         j |= k;
 22     }
 23 
 24     double pi = inverse ? -PI : PI;
 25     for(int step = 1; step < n; step <<= 1) {
 26         // 把每相邻两个“step点DFT”通过一系列蝴蝶操作合并为一个“2*step点DFT”
 27         double alpha = pi / step;
 28         // 为求高效，我们并不是依次执行各个完整的DFT合并，而是枚举下标k
 29         // 对于一个下标k，执行所有DFT合并中该下标对应的蝴蝶操作，即通过E[k]和O[k]计算X[k]
 30         // 蝴蝶操作参考：http://en.wikipedia.org/wiki/Butterfly_diagram
 31         for(int k = 0; k < step; k++) {
 32             // 计算omega^k. 这个方法效率低，但如果用每次乘omega的方法递推会有精度问题。
 33             // 有更快更精确的递推方法，为了清晰起见这里略去
 34             CD omegak = exp(CD(0, alpha*k));
 35             for(int Ek = k; Ek < n; Ek += step << 1) { // Ek是某次DFT合并中E[k]在原始序列中的下标
 36                 int Ok = Ek + step; // Ok是该DFT合并中O[k]在原始序列中的下标
 37                 CD t = omegak * a[Ok]; // 蝴蝶操作：x1 * omega^k
 38                 a[Ok] = a[Ek] - t;  // 蝴蝶操作：y1 = x0 - t
 39                 a[Ek] += t;         // 蝴蝶操作：y0 = x0 + t
 40             }
 41         }
 42     }
 43 
 44     if(inverse)
 45         for(int i = 0; i < n; i++) a[i] /= n;
 46 }
 47 
 48 inline vector<double> operator * (const vector<double>& v1,const vector<double>& v2) {
 49     int s1 = v1.size(),s2=v2.size(),S=2;
 50     while(S < s1 + s2) S <<= 1;
 51     vector<CD> a(S,0), b(S,0); // 把FFT的输入长度补成2的幂，不小于v1和v2的长度之和
 52     for(int i = 0; i < s1; i++) a[i] = v1[i];
 53     FFT(a, false);
 54     for(int i = 0; i < s2; i++) b[i] = v2[i];
 55     FFT(b, false);
 56     for(int i = 0; i < S; i++) a[i] *= b[i];
 57     FFT(a, true);
 58     vector<double> res(s1 + s2 - 1);
 59     for(int i = 0; i < s1 + s2 - 1; i++) res[i] = a[i].real(); // 虚部均为0
 60     return res;
 61 
 62 }
 63 
 64 
 65 const int maxn = 50000 + 10;
 66 int composite[maxn];
 67 
 68 void sieve(int n) {
 69     int m = (int)sqrt(n+0.5);
 70     memset(composite,0,sizeof(composite));
 71     for(int i=2; i<=m; i++) {
 72         if(!composite[i])
 73             for(int j=i*i; j<=n; j+=i)
 74                 composite[j] = 1;
 75     }
 76 }
 77 
 78 const char* suites = "SHCD";
 79 int idx(char suit) {
 80     return strchr(suites,suit)-suites;
 81 }
 82 
 83 int lost[4][maxn];  //4张花色是否丢了
 84 int main() {
 85     sieve(50000);
 86     int a,b,c;
 87     while(scanf("%d%d%d",&a,&b,&c),a) {
 88         memset(lost,0,sizeof(lost));
 89         for(int i=0; i<c; i++) {
 90             int d;
 91             char s;
 92             scanf("%d%c",&d,&s);
 93             lost[idx(s)][d] = 1;
 94         }
 95 
 96         vector<double> ans(1,1),poly;
 97         for(int s=0; s<4; s++) {
 98             poly.clear();
 99             poly.resize(b+1,0);
100             for(int i=4; i<=b; i++) //合数里面挑,并且没有被拿走
101                 if(composite[i]&&!lost[s][i]) poly[i]=1.0;
102             ans = ans*poly;
103             //ans.resize(b+1);
104         }
105         for(int i=a; i<=b; i++)
106             printf("%0.lf
",fabs(ans[i]));
107         puts("");
108     }
109 
110     return 0;
111 }

View Code