10pts求助
查看原帖
10pts求助
1000298
Vsinger_洛天依楼主2024/9/22 20:19
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ll long long
#define re register
#define for_(i,a,b) for(int i=(a);i<=(b);i++)
#define _for(i,a,b) for(int i=(a);i>=(b);i--)
#define lc(q) ((q)<<1)
#define rc(q) ((q)<<1|1)
#define mid(l,r) (((l)+(r))>>1)

using namespace std;

namespace IO {
    inline int read() {
        char ch = getchar();
        int s = 0, f = 1;
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * f;
    }

    inline void write(int x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }

    inline void writeln(int x) {
        write(x);
        putchar('\n');
    }
}

using namespace IO;
const int MAXN = 800005;
const int mod = 167772161;
const int G = 3;
const int Gi = 55924054;


inline int qpow (int a,int b,int c){
	int ans=1;
	while (b){
		if(b&1) ans=1ll*ans*a%c;
		a=1ll*a*a%c;
		b>>=1;
	}
	return ans;
}

int n,k,f[MAXN],g[MAXN],rev[MAXN];

inline void NTT(int *a,int type,int logn){
	int limit=(1<<logn);

	for_(i,0,limit-1) 
        rev[i]=(rev[i>>1]>>1)|((i&1)<<logn-1);

	for_(i,0,limit-1)
		if(i<rev[i]) 
            swap(a[i],a[rev[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		int W=qpow(type==1?G:Gi,(mod-1)/(mid<<1),mod);
		for(int R=mid<<1,j=0;j<limit;j+=R){
			int w=1;
			for_(k,0,mid-1){
				int x=a[j+k],y=1ll*w*a[j+k+mid]%mod;
				a[j+k]=(x+y)%mod;
                a[j+k+mid]=(x+mod-y)%mod;
                w=w*W%mod;
            } 
		} 
	}
	if (type==1) return ; 
	int Inv=qpow(limit,mod-2,mod);
	for_(i,0,limit-1) 
        a[i]=1ll*a[i]*Inv%mod;
}

int b[MAXN],c[MAXN];

inline void INV(int len,int *a,int *b){
	if(len == 1){ 
        b[0]=qpow(a[0],mod-2,mod);
        exit(0);
    }
	INV ((len + 1) >> 1,a,b);
	
    int limit=1,logn=0;
	while(limit<=(len<<1)) 
        limit<<=1,logn++;
	
    for_(i,0,len-1) 
        c[i]=a[i];
	for_(i,len,limit-1) 
        c[i]=0;

	NTT (c,1,logn);NTT(b,1,logn);

	for_(i,0,limit-1) 
        b[i]=1ll*b[i]*(2+mod-1ll*c[i]*b[i]%mod)%mod;

	NTT (b,-1,logn);
	
    for_(i,len,limit-1) 
        b[i]=0;
}

int a[27][2][MAXN];

inline void Solve(int l,int r,int lev,int rnk){
	if(l==r){
		a[lev][rnk][0]=1;
        a[lev][rnk][1]=mod-l;
		exit(0);
	}

	int siz=r-l+1,mid=(l+r)>>1;
    int limit=1,logn=0;

	Solve(l,mid,lev+1,0);
    Solve(mid+1,r,lev+1,1);
	
    while(limit<=siz) 
        limit<<=1,logn++;

	for_(i,mid-l+2,limit) 
        a[lev+1][0][i]=0;
	for_(i,r-mid+1,limit-1) 
        a[lev+1][1][i]=0;

	NTT(a[lev+1][0],1,logn),NTT(a[lev+1][1],1,logn);

	for_(i,0,limit-1) 
        a[lev][rnk][i]=1ll*a[lev+1][0][i]*a[lev+1][1][i]%mod;

	NTT(a[lev][rnk],-1,logn);

	for_(i,siz+1,limit-1) 
        a[lev][rnk][i]=0;
}

int A[MAXN],B[MAXN];

signed main(){
	n=read();k=read();
    if(k>n){
		for_(i,0,n){
            cout << 0 << " ";
        }
        cout << endl;
	}
	else{
		Solve(1,k,0,0);
		for_(i,0,k) 
            A[i]=a[0][0][i];
		INV(n-k+1,A,B);
		for_(i,0,k-1){
            cout << 0 << " ";
        }
		for_(i,0,n-k){
            cout << B[i] << " ";
        }
        cout << endl;
	}
}
2024/9/22 20:19
加载中...