[KOISTUDY] 수열과 쿼리 [2124 / 084C]

http://koistudy.net/?mid=prob_page&NO=2124

KOISTUDY

 

기본적인 틀은 간단하다. $i$~$j$ 범위 안의 $k$ 의 개수를 구하는 것은 우선 merge sort tree 를 형성해주고 

 

 

vector<int> tree[404040];
int n,t=1,q;
 
for(int i=0;i<n;i++)
{
    int a; scanf("%d",&a); tree[t+i].push_back(a);
} for(int i=t-1;i>0;i--)
{
    int siz1=tree[2*i].size(), siz2=tree[2*i+1].size();
    for(int p=0,q=0;p<siz1||q<siz2;)
    {
        if(p==siz1) tree[i].push_back(tree[2*i+1][q]), q++;
        else if(q==siz2) tree[i].push_back(tree[2*i][p]), p++;
        else if(tree[2*i][p]<tree[2*i+1][q]) tree[i].push_back(tree[2*i][p]), p++;
        else tree[i].push_back(tree[2*i+1][q]), q++;
    }
} 

 

 

upper_bound 에서 lower_bound 를 빼는 형식으로 query 를 진행해 $k$ 의 개수, 즉 $X$ 를 구해주면 된다. 

 

 

int query(int st,int en,int num,int node,int l,int r)
{
    if(r<st||en<l) return 0;
    if(st<=l&&r<=en)
    {
        return upper_bound(tree[node].begin(),tree[node].end(),num)
        -lower_bound(tree[node].begin(),tree[node].end(),num);
    } int mid=(l+r)/2;
    return query(st,en,num,2*node,l,mid)+query(st,en,num,2*node+1,mid+1,r);
}

 

이를 해결하기 위하여 우선 $_{X*k}C_{k}$ 가 2017의 배수인지부터 확인해주자. 2017은 다행이도 소수이므로 어떤 수에 대해서 2017의 배수의 개수, 2017*2017의 배수의 개수... 등을 확인해주면 된다. 이때 $n\leq100,000$ 이므로 $X*k$ 가 int 범위를 넘을 수 있어 long long 으로 형변환해주어야 한다. 만약 $_{X*k}C_{k}$ 가 2017의 배수라면 2017로 나눈 나머지는 0이므로 0을 출력해주자. 

 

 

#define MOD 2017
 
int gesu(ll p)
{
    ll ret=0;
    while(p)
    {
        p/=MOD; ret+=p;
    } return (int)ret;
}
 
if(gesu(1LL*X*k)-gesu(1LL*X*k-1LL*k)-gesu(1LL*k)!=0) puts("0");

 

 

2017로 나눈 나머지가 0이 아니라면 $_{X*k}C_{k}$ 를 실제로 2017로 나눈 값을 구해야 한다. 이때 2017의 배수가 곱해지지 않도록 하는 것이 관건이다. 이는 2016! 을 기본 단위로 하여 곱하는 것에서 해결할 수 있다. 예를 들어 $_{4040}C_{2030}$ 을 계산한다고 하자. 4040! 에서 2017이 빠진 수를 곱해야 하니 ${2016!}^2$ 를 하고 나머지 $6!$ 을 곱해주며 또한 2017 과 4034 를 지우면서 발생한 1*2 도 곱해주어야 한다. 이렇게 팩토리얼을 계산해주면 $O(NlogN)$ 이라는 시간복잡도 안에 답을 구할 수 있다. 

 

 

#include <bits/stdc++.h>
#define MOD 2017
using namespace std;
typedef long long ll;
vector<int> tree[404040];
int n,t=1,q,fac[7070];
int jegob(int p,ll q)
{
    if(q==0) return 1;
    int ret=jegob(p,q/2);
    if(q%2) return ((ret*ret)%MOD)*p%MOD;
    return ret*ret%MOD;
} int query(int st,int en,int num,int node,int l,int r)
{
    if(r<st||en<l) return 0;
    if(st<=l&&r<=en)
    {
        return upper_bound(tree[node].begin(),tree[node].end(),num)
        -lower_bound(tree[node].begin(),tree[node].end(),num);
    } int mid=(l+r)/2;
    return query(st,en,num,2*node,l,mid)+query(st,en,num,2*node+1,mid+1,r);
} int gesu(ll p)
{
    ll ret=0;
    while(p)
    {
        p/=MOD; ret+=p;
    } return (int)ret;
}
main()
{
    scanf("%d",&n); while(t<n) t*=2;
    for(int i=0;i<n;i++)
    {
        int a; scanf("%d",&a); tree[t+i].push_back(a);
    } for(int i=t-1;i>0;i--)
    {
        int siz1=tree[2*i].size(), siz2=tree[2*i+1].size();
        for(int p=0,q=0;p<siz1||q<siz2;)
        {
            if(p==siz1) tree[i].push_back(tree[2*i+1][q]), q++;
            else if(q==siz2) tree[i].push_back(tree[2*i][p]), p++;
            else if(tree[2*i][p]<tree[2*i+1][q]) tree[i].push_back(tree[2*i][p]), p++;
            else tree[i].push_back(tree[2*i+1][q]), q++;
        }
    } scanf("%d",&q); fac[0]=1;
    for(int i=1;i<=MOD-1;i++) fac[i]=fac[i-1]*i, fac[i]%=MOD;
    while(q--)
    {
        int a,b,k; scanf("%d%d%d",&a,&b,&k);
        int X=query(a-1,b-1,k,1,0,t-1);
        if(X==0) puts("0");
        else if(X==1) puts("1");
        else if(gesu(1LL*X*k)-gesu(1LL*X*k-1LL*k)-gesu(1LL*k)!=0) puts("0");
        else 
        {
            int st=1,en=1;
            ll imsi=1LL*X*k;
            while(imsi)
            {
                st*=jegob(fac[MOD-1],imsi/MOD); st%=MOD;
                st*=fac[imsi%MOD]; st%=MOD;
                imsi/=MOD;    
            } imsi=1LL*k;
            while(imsi)
            {
                en*=jegob(fac[MOD-1],imsi/MOD); en%=MOD;
                en*=fac[imsi%MOD]; en%=MOD;
                imsi/=MOD;    
            } imsi=1LL*X*k-1LL*k;
            while(imsi)
            {
                en*=jegob(fac[MOD-1],imsi/MOD); en%=MOD;
                en*=fac[imsi%MOD]; en%=MOD;
                imsi/=MOD;    
            } st*=jegob(en,MOD-2); st%=MOD; printf("%d\n",st);
        }
    }
}