#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<pair<lng,lng>,null_type,less<pair<lng,lng>>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<double,null_type,less<double>,rb_tree_tag,tree_order_statistics_node_update>
#define rtr return 0
#define lng long long
#define double long double
#define endl "\n"
#define pb push_back
#define cmbntrcs fact[0]=1;for(int i=1;i<INF;i++){fact[i]=mul(i,fact[i-1]);}inv[INF-1]=mod_inv(fact[INF-1]);for(int i=INF-2;i>=0;i--){inv[i]=mul(inv[i+1],i+1);}
///#pragma GCC optimize(Ofast,unroll-all-loops)
const int INF=1e6+7,SZ=3e5+7,MSZ=1e5+3,MAXA=6e5+7;
int MOD=998244353;
int add(int x,int y){int z=x+y;if(z>=MOD){z-=MOD;}return z;}
int sub(int x,int y){int z=x-y;if(z<0){z+=MOD;}return z;}
int mul(int x,int y){return(x*1ll*y)%MOD;}
int pwr(int a,lng b)
{
int rs=1;
while(b>0){if(b&1){rs=mul(rs,a);}a=mul(a,a);b>>=1;}
return rs;
}
int mod_inv(int a){return pwr(a,MOD-2);}
int fact[INF],inv[INF];
int nCr(int n,int r){if(r>n||r<0||n<0){return 0;}return mul(fact[n],mul(inv[r],inv[n-r]));}
int nPr(int n,int r){if(r>n||r<0||n<0){return 0;}return mul(fact[n],inv[n-r]);}
int nPrvc(vector<int>r)
{
int den=1,n=0;
for(int i=0;i<r.size();i++){den=mul(den,inv[r[i]]);n+=r[i];}
return mul(fact[n],den);
}
int sb(int s,int b){if(s<0||b<0){return 0;}return nCr(s+b-1,s);}
int prfx(int i,int j){if(i<0||j<0){return 0;}return nCr(i+j,i);}
int nCrL(int x,int y)
{
int rt=1;for(int i=x;i>x-y;i--){rt=mul(rt,i);}
int dn=1;for(int i=1;i<=y;i++){dn=mul(dn,i);}
return mul(rt,mod_inv(dn));
}
lng lcm(lng x,lng y){return((x/__gcd(x,y))*y);}
lng trig(lng x){return x*(x+1)/2;}
lng pent(lng x){return(x*((3*x)-1))/2;}
lng sigma(lng x,lng y){return trig(y)-trig(x-1);}
pair<double,double>quad(double a,double b,double c)
{
double disc=(b*b)-(4*a*c);
if(disc<0){return{-1e16,-1e16};}
return{(sqrt(disc)-b)/(2*a),-(sqrt(disc)+b)/(2*a)};
}
double sigma_rev(double x){return quad(1,1,-2*x).first;}
lng cldv(lng a,lng b){return(a+b-1)/b;}
lng fp(lng a,lng b)
{
lng rs=1;
while(b>0){if(b&1){rs*=a;}a*=a;b>>=1;}
return rs;
}
struct mtrx
{
lng nx,mx;vector<vector<lng>>bd;
void bld(vector<vector<lng>>obd){nx=obd.size(),mx=obd[0].size();bd=obd;}
void outm(){for(lng i=0;i<nx;i++){for(lng j=0;j<mx;j++){cout << bd[i][j] << ' ';}cout << endl;}}
};
mtrx idnt(lng n)
{
vector<vector<lng>>v;v.resize(n);
for(lng i=0;i<n;i++){v[i].assign(n,0);v[i][i]=1;}
return{n,n,v};
}
mtrx mulm(mtrx a,mtrx b)
{
if(a.mx!=b.nx){return{1,1,{{0}}};}
vector<vector<lng>>v;v.resize(a.nx);
for(lng i=0;i<a.nx;i++)
{
v[i].resize(b.mx);
for(lng j=0;j<b.mx;j++)
{
lng s=0;
for(lng x=0;x<a.mx;x++)
{
s+=a.bd[i][x]*b.bd[x][j];
s%=MOD;
}
v[i][j]=s;
}
}
mtrx ret;ret.bld(v);
return ret;
}
mtrx fpm(mtrx a,lng b)
{
if(b==0){return idnt(a.nx);}
mtrx ret=fpm(a,b/2);ret=mulm(ret,ret);
if(b%2){ret=mulm(ret,a);}
return ret;
}
lng rndm(lng a,lng b){return a+rng()%((b+1)-a);}
struct dsu
{
vector<lng>p,sz;
void init(lng n)
{
p.resize(n+1);sz.assign(n+1,1);
for(lng i=0;i<=n;i++){p[i]=i;}
return;
}
lng get(lng a)
{
if(p[a]==a){return a;}
return p[a]=get(p[a]);
}
void unn(lng x,lng y)
{
if(cnct(x,y)){return;}
x=get(x);y=get(y);
if(sz[x]>sz[y]){swap(x,y);}
p[x]=y;sz[y]+=sz[x];return;
}
bool cnct(lng x,lng y){return get(x)==get(y);}
lng siz(lng a){return sz[get(a)];}
};
lng a[SZ],f[INF]{},ans[INF]{},n,k;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;for(lng i=0;i<n;i++){cin >> a[i];f[a[i]]++;}
for(lng i=k+1;i<INF;i++)
{
for(lng j=0;(i*j)+k<INF;j++){ans[(i*j)+k]+=f[i];}
}
for(int i=0;i<n;i++){cout << ans[a[i]]-int64_t(k==0) << ' ';}
return 0;
}
Compilation message
spiderman.cpp: In function 'int nPrvc(std::vector<int>)':
spiderman.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<r.size();i++){den=mul(den,inv[r[i]]);n+=r[i];}
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
37 ms |
11132 KB |
Output is correct |
| 2 |
Correct |
42 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
67 ms |
12924 KB |
Output is correct |
| 4 |
Correct |
114 ms |
16192 KB |
Output is correct |
| 5 |
Correct |
80 ms |
17612 KB |
Output is correct |
| 6 |
Correct |
114 ms |
21128 KB |
Output is correct |
| 7 |
Correct |
62 ms |
17552 KB |
Output is correct |
| 8 |
Correct |
74 ms |
17556 KB |
Output is correct |
| 9 |
Correct |
127 ms |
21000 KB |
Output is correct |
| 10 |
Correct |
107 ms |
20900 KB |
Output is correct |
