fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MD 1000000007
  4. void *wmem;
  5. template<class T> void malloc1d(T **arr, int x, void **mem = &wmem){
  6.   (*arr)=(T*)(*mem);
  7.   (*mem)=((*arr)+x);
  8. }
  9. struct mint{
  10.   static unsigned R, RR, Rinv, W, md, mdninv;
  11.   unsigned val;
  12.   mint(){
  13.   }
  14.   mint(int a){
  15.     val = mulR(a);
  16.   }
  17.   mint(unsigned a){
  18.     val = mulR(a);
  19.   }
  20.   mint(long long a){
  21.     val = mulR(a);
  22.   }
  23.   mint(unsigned long long a){
  24.     val = mulR(a);
  25.   }
  26.   int get_inv(long long a, int md){
  27.     long long e, s=md, t=a, u=1, v=0;
  28.     while(s){
  29.       e=t/s;
  30.       t-=e*s;
  31.       u-=e*v;
  32.       swap(t,s);
  33.       swap(u,v);
  34.     }
  35.     if(u<0){
  36.       u+=md;
  37.     }
  38.     return u;
  39.   }
  40.   void setmod(unsigned m){
  41.     int i;
  42.     unsigned t;
  43.     W = 32;
  44.     md = m;
  45.     R = (1ULL << W) % md;
  46.     RR = (unsigned long long)R*R % md;
  47.     switch(m){
  48.       case 104857601:
  49.       Rinv = 2560000;
  50.       mdninv = 104857599;
  51.       break;
  52.       case 998244353:
  53.       Rinv = 232013824;
  54.       mdninv = 998244351;
  55.       break;
  56.       case 1000000007:
  57.       Rinv = 518424770;
  58.       mdninv = 2226617417U;
  59.       break;
  60.       case 1000000009:
  61.       Rinv = 171601999;
  62.       mdninv = 737024967;
  63.       break;
  64.       case 1004535809:
  65.       Rinv = 234947584;
  66.       mdninv = 1004535807;
  67.       break;
  68.       case 1007681537:
  69.       Rinv = 236421376;
  70.       mdninv = 1007681535;
  71.       break;
  72.       case 1012924417:
  73.       Rinv = 238887936;
  74.       mdninv = 1012924415;
  75.       break;
  76.       case 1045430273:
  77.       Rinv = 254466304;
  78.       mdninv = 1045430271;
  79.       break;
  80.       case 1051721729:
  81.       Rinv = 257538304;
  82.       mdninv = 1051721727;
  83.       break;
  84.       default:
  85.       Rinv = get_inv(R, md);
  86.       mdninv = 0;
  87.       t = 0;
  88.       for(i=0;i<(int)W;i++){
  89.         if(t%2==0){
  90.           t+=md;
  91.           mdninv |= (1U<<i);
  92.         }
  93.         t /= 2;
  94.       }
  95.     }
  96.   }
  97.   unsigned mulR(unsigned a){
  98.     return (unsigned long long)a*R%md;
  99.   }
  100.   unsigned mulR(int a){
  101.     if(a < 0){
  102.       a = a%md+md;
  103.     }
  104.     return mulR((unsigned)a);
  105.   }
  106.   unsigned mulR(unsigned long long a){
  107.     return mulR((unsigned)(a%md));
  108.   }
  109.   unsigned mulR(long long a){
  110.     a %= md;
  111.     if(a < 0){
  112.       a += md;
  113.     }
  114.     return mulR((unsigned)a);
  115.   }
  116.   unsigned reduce(unsigned T){
  117.     unsigned m=T * mdninv, t=(unsigned)((T + (unsigned long long)m*md) >> W);
  118.     if(t >= md){
  119.       t -= md;
  120.     }
  121.     return t;
  122.   }
  123.   unsigned reduce(unsigned long long T){
  124.     unsigned m=(unsigned)T * mdninv, t=(unsigned)((T + (unsigned long long)m*md) >> W);
  125.     if(t >= md){
  126.       t -= md;
  127.     }
  128.     return t;
  129.   }
  130.   unsigned get(){
  131.     return reduce(val);
  132.   }
  133.   mint &operator+=(mint a){
  134.     val += a.val;
  135.     if(val >= md){
  136.       val -= md;
  137.     }
  138.     return *this;
  139.   }
  140.   mint &operator-=(mint a){
  141.     if(val < a.val){
  142.       val = val + md - a.val;
  143.     }
  144.     else{
  145.       val -= a.val;
  146.     }
  147.     return *this;
  148.   }
  149.   mint &operator*=(mint a){
  150.     val = reduce((unsigned long long)val*a.val);
  151.     return *this;
  152.   }
  153.   mint &operator/=(mint a){
  154.     return *this *= a.inverse();
  155.   }
  156.   mint operator+(mint a){
  157.     return mint(*this)+=a;
  158.   }
  159.   mint operator-(mint a){
  160.     return mint(*this)-=a;
  161.   }
  162.   mint operator*(mint a){
  163.     return mint(*this)*=a;
  164.   }
  165.   mint operator/(mint a){
  166.     return mint(*this)/=a;
  167.   }
  168.   mint operator+(int a){
  169.     return mint(*this)+=mint(a);
  170.   }
  171.   mint operator-(int a){
  172.     return mint(*this)-=mint(a);
  173.   }
  174.   mint operator*(int a){
  175.     return mint(*this)*=mint(a);
  176.   }
  177.   mint operator/(int a){
  178.     return mint(*this)/=mint(a);
  179.   }
  180.   mint operator+(long long a){
  181.     return mint(*this)+=mint(a);
  182.   }
  183.   mint operator-(long long a){
  184.     return mint(*this)-=mint(a);
  185.   }
  186.   mint operator*(long long a){
  187.     return mint(*this)*=mint(a);
  188.   }
  189.   mint operator/(long long a){
  190.     return mint(*this)/=mint(a);
  191.   }
  192.   mint operator-(void){
  193.     mint res;
  194.     if(val){
  195.       res.val=md-val;
  196.     }
  197.     else{
  198.       res.val=0;
  199.     }
  200.     return res;
  201.   }
  202.   operator bool(void){
  203.     return val!=0;
  204.   }
  205.   operator int(void){
  206.     return get();
  207.   }
  208.   operator long long(void){
  209.     return get();
  210.   }
  211.  
  212.   mint inverse(){
  213.     int a = val, b = md, u = 1, v = 0, t;
  214.     mint res;
  215.     while(b){
  216.       t = a / b;
  217.       a -= t * b; swap(a, b);
  218.       u -= t * v; swap(u, v);
  219.     }
  220.     if(u < 0) u += md;
  221.     res.val = (unsigned long long)u*RR % md;
  222.     return res;
  223.   }
  224.  
  225.   mint pw(unsigned long long b){
  226.     mint a(*this), res;
  227.     res.val = R;
  228.     while(b){
  229.       if(b&1) res *= a;
  230.       b >>= 1;
  231.       a *= a;
  232.     }
  233.     return res;
  234.   }
  235.  
  236.   bool operator==(int a){return mulR(a)==val;}
  237.   bool operator!=(int a){return mulR(a)!=val;}
  238. };
  239. unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;
  240. mint operator+(int a, mint b){return mint(a)+=b;
  241. }
  242. mint operator-(int a, mint b){
  243.   return mint(a)-=b;
  244. }
  245. mint operator*(int a, mint b){
  246.   return mint(a)*=b;
  247. }
  248. mint operator/(int a, mint b){
  249.   return mint(a)/=b;
  250. }
  251. mint operator+(long long a, mint b){
  252.   return mint(a)+=b;
  253. }
  254. mint operator-(long long a, mint b){
  255.   return mint(a)-=b;
  256. }
  257. mint operator*(long long a, mint b){
  258.   return mint(a)*=b;
  259. }
  260. mint operator/(long long a, mint b){
  261.   return mint(a)/=b;
  262. }
  263. void rd(int &x){
  264.   int k, m=0;
  265.   x=0;
  266.   for(;;){
  267.     k = getchar_unlocked();
  268.     if(k=='-'){
  269.       m=1;
  270.       break;
  271.     }
  272.     if('0'<=k&&k<='9'){
  273.       x=k-'0';
  274.       break;
  275.     }
  276.   }
  277.   for(;;){
  278.     k = getchar_unlocked();
  279.     if(k<'0'||k>'9'){
  280.       break;
  281.     }
  282.     x=x*10+k-'0';
  283.   }
  284.   if(m){
  285.     x=-x;
  286.   }
  287. }
  288. int rd(char c[]){
  289.   int i, sz=0;
  290.   for(;;){
  291.     i = getchar_unlocked();
  292.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  293.       break;
  294.     }
  295.   }
  296.   c[sz++] = i;
  297.   for(;;){
  298.     i = getchar_unlocked();
  299.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  300.       break;
  301.     }
  302.     c[sz++] = i;
  303.   }
  304.   c[sz]='\0';
  305.   return sz;
  306. }
  307. void wt_L(int x){
  308.   char f[10];
  309.   int m=0, s=0;
  310.   if(x<0){
  311.     m=1;
  312.     x=-x;
  313.   }
  314.   while(x){
  315.     f[s++]=x%10;
  316.     x/=10;
  317.   }
  318.   if(!s){
  319.     f[s++]=0;
  320.   }
  321.   if(m){
  322.     putchar_unlocked('-');
  323.   }
  324.   while(s--){
  325.     putchar_unlocked(f[s]+'0');
  326.   }
  327. }
  328. void wt_L(mint x){
  329.   int i;
  330.   i = (int)x;
  331.   wt_L(i);
  332. }
  333. struct combination_mint{
  334.   mint *fac, *ifac;
  335.   void init(int n, void **mem = &wmem){
  336.     int i;
  337.     malloc1d(&fac, n, mem);
  338.     malloc1d(&ifac, n, mem);
  339.     fac[0] = 1;
  340.     for(i=1;i<n;i++){
  341.       fac[i] = fac[i-1] * i;
  342.     }
  343.     ifac[n-1] = 1 / fac[n-1];
  344.     for(i=n-2;i>=0;i--){
  345.       ifac[i] = ifac[i+1] * (i+1);
  346.     }
  347.   }
  348.   mint C(int a, int b){
  349.     if(b < 0 || b > a){
  350.       return 0;
  351.     }
  352.     return fac[a]*ifac[b]*ifac[a-b];
  353.   }
  354.   mint P(int a, int b){
  355.     if(b < 0 || b > a){
  356.       return 0;
  357.     }
  358.     return fac[a]*ifac[a-b];
  359.   }
  360.   mint H(int a, int b){
  361.     if(a==0 && b==0){
  362.       return 1;
  363.     }
  364.     if(a<=0 || b<0){
  365.       return 0;
  366.     }
  367.     return C(a+b-1, b);
  368.   }
  369. }
  370. ;
  371. char S[500010], memarr[64000000];
  372. int N, Q;
  373. int main(){
  374.   combination_mint comb;
  375.   int hist[4];
  376.   mint ab, cd, res;
  377.   wmem = memarr;
  378.   {
  379.     mint x;
  380.     x.setmod(MD);
  381.   }
  382.   comb.init(500010);
  383.   rd(Q);
  384.   while(Q--){
  385.     N = rd(S);
  386.     {
  387.       int Lj4PdHRW;
  388.       for(Lj4PdHRW=0;Lj4PdHRW<(3) + 1;Lj4PdHRW++){
  389.         hist[Lj4PdHRW] = 0;
  390.       }
  391.     }
  392.     {
  393.       int KL2GvlyY;
  394.       for(KL2GvlyY=0;KL2GvlyY<(N-1) + 1;KL2GvlyY++){
  395.         hist[S[KL2GvlyY]-'a']++;
  396.       }
  397.     }
  398.     ab = cd = 0;
  399.     {
  400.       int Q5VJL1cS;
  401.       for(Q5VJL1cS=0;Q5VJL1cS<(N) + 1;Q5VJL1cS++){
  402.         ab += comb.C(hist[0],(Q5VJL1cS)) * comb.C(hist[1],(Q5VJL1cS));
  403.       }
  404.     }
  405.     {
  406.       int e98WHCEY;
  407.       for(e98WHCEY=0;e98WHCEY<(N) + 1;e98WHCEY++){
  408.         cd += comb.C(hist[2],(e98WHCEY)) * comb.C(hist[3],(e98WHCEY));
  409.       }
  410.     }
  411.     res = ab * cd - 1;
  412.     wt_L(res);
  413.     putchar_unlocked('\n');
  414.   }
  415.   return 0;
  416. }
  417. // cLay varsion 20170505-2
  418.  
  419. // --- original code ---
  420. // int Q, N;
  421. // char S[500010];
  422. // {
  423. //   int hist[4];
  424. //   combination_mint comb;
  425. //   mint res, ab, cd;
  426. // 
  427. //   comb.init(500010);
  428. // 
  429. //   rd(Q);
  430. //   while(Q--){
  431. //     rd(S@N);
  432. // 
  433. //     hist[0..3] = 0;
  434. //     hist[S[0..N-1]-'a']++;
  435. // 
  436. //     ab = cd = 0;
  437. //     ab += comb.C(hist[0],(0..N)) * comb.C(hist[1],(0..));
  438. //     cd += comb.C(hist[2],(0..N)) * comb.C(hist[3],(0..));
  439. //     
  440. //     res = ab * cd - 1;
  441. //     wt(res);
  442. //   }
  443. // }
  444.  
Time limit exceeded #stdin #stdout 5s 78208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3DuGUi
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!