fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define vll vector<ll >
  6. #define vvi vector<vi >
  7. #define int long long int
  8.  
  9. int N, K, a, b;
  10. int p[100000+100], qual[100000+10];
  11. int mod = 786433, g = 10, w = 1000;
  12. ll pw[(1<<18)],ans[786434];
  13.  
  14. ll powr(ll a, ll b, ll mod)
  15. {
  16.     ll x = 1%mod;
  17.     a %= mod;
  18.     while(b)
  19.     {
  20.         if(b&1)
  21.             x = (x*a)%mod;
  22.         a = (a*a)%mod;
  23.         b >>= 1;
  24.     }
  25.     return x;
  26. }
  27. ll inv(ll a, ll mod)
  28. {
  29.     return powr(a,mod-2,mod);
  30. }
  31.  
  32. const int maxn = 1e6+10;
  33.  
  34. void mul_naive(vll& a, vll& b)
  35. {
  36.     vll c(a.size()+b.size()-1);
  37.     for(int i = 0;i<a.size();i++)
  38.         for(int j = 0;j<b.size();j++)
  39.             c[i+j]+=a[i]*b[j];
  40.     a = c;  
  41. }
  42.  
  43. class NTT{
  44.  
  45.     ll p,g,n,logn;
  46. public:
  47.     NTT(ll P, ll G, ll LOGN)    
  48.     {
  49.         p = P;
  50.         ll g1 = G;
  51.         logn = LOGN;
  52.         n = (1<<LOGN);
  53.         assert((p-1)%n == 0);
  54.         g = powr(g1,(p-1)>>logn,p);
  55.     }
  56.  
  57.     int bitrevcopy(int i)
  58.     {
  59.         int ret = 0;
  60.         for(int j = 0;j<logn;j++)
  61.             if(i&(1<<j))
  62.                 ret|=(1<<(logn-1-j));
  63.         return ret;
  64.     }
  65.     void fft(vll& a, bool invert)
  66.     {   
  67.         ll mod = p;
  68.         for(int i = 0;i<n;i++)
  69.         {
  70.             int br = bitrevcopy(i);
  71.             if(i<br)
  72.                 swap(a[i],a[br]);
  73.         }
  74.         for(int i = 1;i<=logn;i++)
  75.         {
  76.             ll mul = powr(g,1<<(logn-i),p);
  77.             if(invert)
  78.                 mul = inv(mul,p);
  79.             int add = (1<<i);
  80.             for(int k = 0;k<n;k+=add)
  81.             {
  82.                 ll w = 1;
  83.                 ll lim = (add>>1);
  84.                 for(int j = 0;j<lim;j++)
  85.                 {
  86.                     ll u = (w*a[k+j+lim])%p, v = a[k+j];
  87.                     a[k+j] = u+v;
  88.                     if(a[k+j]>=p)
  89.                         a[k+j] -= p;
  90.                     a[k+j+lim] = v-u;
  91.                     if(a[k+j+lim]<0)
  92.                         a[k+j+lim]+=p;
  93.                     w = (w*mul)%p;
  94.                 }
  95.             }
  96.         }
  97.         if(invert){
  98.             ll _inv = inv(n,p);
  99.             for(int i = 0;i<n;i++){
  100.                 a[i] = (a[i]*_inv)%p;
  101.             }
  102.         }
  103.     }
  104. };
  105. void NTT_mul(vll& a, vll& B)
  106. {
  107.     vll b = B;
  108.     int _sz = a.size()+b.size()-1;
  109.     int LOGN = 0;
  110.     while((1<<LOGN) < _sz)
  111.         LOGN++;
  112.     ll N = (1<<LOGN);
  113.     a.resize(N);
  114.     b.resize(N);
  115.     NTT fft1 = NTT(mod,g,LOGN);
  116.     fft1.fft(a,false);
  117.     fft1.fft(b,false);
  118.     for(int i = 0;i<N;i++){
  119.         a[i] = (a[i]*b[i])%mod;
  120.     }
  121.     fft1.fft(a,true);
  122.     a.resize(_sz);
  123. }   
  124.  
  125. void polymulmod(vll& a, vll& b, bool takemod, ll mod, bool give_a_fuck_about_precision)
  126. {
  127.     int sa=a.size(),sb=b.size();
  128.  
  129.     if(sa*1ll*sb <= 100000)
  130.         mul_naive(a,b);
  131.     else NTT_mul(a,b);
  132.     if(takemod)
  133.         for(int i = 0;i<a.size();i++)
  134.             a[i]%=mod;
  135. }
  136. vll solve(int l,int r)
  137. {
  138.     if(l==r)
  139.         return {1-p[l],p[l]};
  140.     int m = (l+r)>>1;
  141.     vll v1 = solve(l,m);
  142.     vll v2 = solve(m+1,r);
  143.     polymulmod(v1,v2,1,mod,1);
  144.     return v1;
  145. }
  146. main()
  147. {
  148.     // clock_t clk = clock();
  149.     //ios_base::sync_with_stdio(false);
  150.     //cin.tie(NULL);
  151.     scanf("%lld %lld",&N,&K);
  152.     for( int i=0 ; i < N ; i++ ){ scanf("%lld %lld %lld",&a,&b,&qual[i]); p[i]=a*inv(b,mod)%mod; }
  153.     vll a = solve(0, N-1);
  154.     int nn = K;
  155.   vll poly(K);
  156.   int c = 1;
  157.   for(int i=0;i<K;i++)
  158.   {
  159.     poly[i] = c*a[K-1-i];
  160.     c*=(-1);
  161.   }
  162.   poly.resize(mod);
  163.   NTT fft1 = NTT(mod,10,18);
  164.     vll poly1(mod);
  165.   c = 1;
  166.   for(int i=0;i<mod;i++)
  167.   {
  168.         poly1[i] = (poly[i]*c)%mod;
  169.         c = (c*10)%mod;
  170.   }
  171.   vll poly2(mod);
  172.   c = 1;
  173.   for(int i=0;i<mod;i++)
  174.   {
  175.         poly2[i] = (poly[i]*c)%mod;
  176.         c = (c*100)%mod;
  177.   }
  178.   fft1.fft(poly,false);
  179.   fft1.fft(poly1,false);
  180.   fft1.fft(poly2,false);
  181.   int root = 1000;
  182.   pw[0] = 1;
  183.   for(int i = 1; i < (1 << 18); i++)
  184.         pw[i] = (pw[i - 1] * root) % mod;
  185.     for(int i = 0; i < (1 << 18); i++) {
  186.         ans[pw[i]] = poly[i];
  187.         ans[pw[i] * 10 % mod] = poly1[i];
  188.         ans[pw[i] * 100 % mod] = poly2[i];
  189.     }
  190.     ll answer = 0;
  191. for(int i=0;i<N;i++)
  192. {if(p[i]==1)answer+=a[K]*1ll*qual[i];
  193. else if(p[i] != 0)
  194.   {   ll x = (p[i]*1ll*inv(1-p[i],mod))%mod;
  195.     if(x<0)x += mod;
  196.     answer += (ans[x]*1ll*x%mod)*1ll*qual[i]%mod;
  197.     //cout<<(ans[x]*1ll*x%mod)<<endl;
  198.   }
  199.   answer %= mod;
  200.   //cout<<a[K]+mod<<endl;
  201. }
  202.     answer = (answer+mod)%mod;
  203.   cout<<answer;
  204.   //cerr<<(float)(clock()-clk)/CLOCKS_PER_SEC;
  205.     return 0;
  206. }
Success #stdin #stdout 0.2s 29548KB
comments (?)
stdin
copy 
3 2
1 2 4
1 3 4
1 3 6
stdout
copy 
87384
https://ideone.com/v690Kx
language:
C++14 (gcc 8.3)
created:
6 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!