QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#630690#3840. Pass the Ball!karito#Compile Error//C++203.4kb2024-10-11 20:00:532024-10-11 20:00:53

Judging History

This is the latest submission verdict.

  • [2024-10-11 20:00:53]
  • Judged
  • [2024-10-11 20:00:53]
  • Submitted

answer


#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
namespace FFT{

const int MAXB=19;
const int MAXN=(1<<MAXB);
int pbd[MAXN];

int bit_rev(int x,int b)
{
    int ans=0;
    for(int i=0;i<b;i++)
    {
        ans=(ans<<1)|(x&1);
        x>>1;
    }
    return ans;
}

int cmp_b;

bool bit_cmp(int x,int y)
{
    return bit_rev(x,cmp_b)<bit_rev(y,cmp_b);
}

const double pi=acos(-1);

complex<double> w(int n,int m)
{
    double phi=2*pi/n*m;
    return complex<double>{cos(phi),sin(phi)};
}

void pre(int b)
{
    int n=(1<<b);
    for(int i=0;i<n;i++)
        pbd[i]=(pbd[i>>1]>>1)|((i&1)<<(b-1));
}

void fft(vector<complex<double>>::iterator a,int b)
{
    int n=(1<<b);
    for(int i=0;i<n;i++)
        if(i<pbd[i])
            swap(a[i],a[pbd[i]]);
    for(int i=1;i<=b;i++)
    {
        for(int j=0;j<n;j+=(1<<i))
        {
            int t=(1<<i),s=t>>1;
            for(int k=0;k<s;k++)
            {
                auto a0=a[k+j],a1=a[k+j+s];
                auto wi=w(t,k);
                a[k+j]=a0+a1*wi;
                a[k+j+s]=a0-a1*wi;
            }
        }
    }
    return;
}

void ifft(vector<complex<double>>::iterator a,int b)
{
    fft(a,b);
    int n=(1<<b);
    reverse(a+1,a+n);
    for(int i=0;i<n;i++)
        a[i]/=n;
    return;
}

}

using namespace FFT;

int a[MAXN];
int vis[MAXN];
vector<complex<double>>t[MAXN];
vector<long long>ans[MAXN];
int sza[MAXN];
int szcnt=0;
map<int,int> mp;
int cnt=0;
void dfs(int x){
    if(vis[x]) return;
    t[cnt].push_back(x);
    vis[x]=1;
    dfs(a[x]);
}
signed main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt++;
            dfs(i);
            int sz = t[cnt].size();
            t[cnt+1] = t[cnt];
            reverse(t[cnt+1].begin(),t[cnt+1].end());
            int b = 1;
            while((1<<b)<sz*2) b++;
            pre(b);
            t[cnt].resize(1<<(b));
            t[cnt+1].resize(1<<(b));
            
            // cout<<b<<" "<<sz<<endl;
            // for(int i=0;i<sz;i++){
            //     cout<<t[cnt][i].real()<<" "<<t[cnt+1][i].real()<<endl;
            // }

            fft(t[cnt].begin(),b);
            fft(t[cnt+1].begin(),b);

            for(int i=0;i<(1<<(b));i++){
                t[cnt][i]=t[cnt][i]*t[cnt+1][i];
            }
            ifft(t[cnt].begin(),b);
            
            // cout<<endl;
            // for(int i=0;i<1<<(b);i++){
            //     cout<<i<<" "<<t[cnt][i].real()<<endl;
            // }

            if(!mp.count(sz)){
                szcnt++;
                sza[szcnt]=sz;
                mp[sz]=szcnt;
                ans[szcnt].resize(sz);
            }
            int id=mp[sz];
            ans[id][0]+=(long long)(t[cnt][sz-1].real()+0.5);
            for(int j=1;j<sz;j++){
                ans[id][j]+=(long long)(t[cnt][j-1].real()+0.5)+(long long)(t[cnt][sz-1+j].real()+0.5);
            }
            
            for(int i=0;i<(1<<(b));i++) pbd[i] = 0;

            cnt++;
        }
    }
    for(int i=1;i<=q;i++){
        int k;
        cin>>k;
        ll res = 0;
        for(int j=1;j<=szcnt;j++){
            res += ans[j][k%(sza[j])];
            
        }
        // cout<<ans[2][k%3]<<endl;
        cout<<res<<endl;
    }
}

詳細信息

answer.code: In function ‘int main()’:
answer.code:150:9: error: ‘ll’ was not declared in this scope
  150 |         ll res = 0;
      |         ^~
answer.code:152:13: error: ‘res’ was not declared in this scope
  152 |             res += ans[j][k%(sza[j])];
      |             ^~~
answer.code:156:15: error: ‘res’ was not declared in this scope
  156 |         cout<<res<<endl;
      |               ^~~