QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377430#6196. Minimum Element ProblemlexiyvvCompile Error//C++143.5kb2024-04-05 13:31:122024-04-05 13:31:12

Judging History

你现在查看的是最新测评结果

  • [2024-04-05 13:31:12]
  • 评测
  • [2024-04-05 13:31:12]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,f[1000005],m,g[1000005],w[1000005],e[1000005],u1[1000005],u2[1000005],all[1000005];
int jc[1000005],inv[1000005];
int fm(int x,int y){
	int res=1;
	while(y){
		if(y&1)(res*=x)%=mod;
		(x*=x)%=mod,y/=2;
	}
	return res;
}
void init(){
    jc[0]=jc[1]=1;
    for(int i=2;i<=1000001;i++)
    jc[i]=(jc[i-1]%mod*i%mod)%mod;
    for(int i=0;i<=1000001;i++)inv[i]=fm(jc[i],mod-2);
}
long long C(int a,int b){
    return jc[a]%mod*inv[b]%mod*inv[a-b]%mod;
}
	const int NR = 1 << 22, gg = 3, gi = 332748118;
struct{
	typedef long long ll;
	int n, m, rev[NR+5];
	long long a[NR+5], b[NR+5];
	ll fast_power(ll a, ll k)
	{
	    ll res = 1;
	    while (k)
	    {
	        if (k & 1)
	            res = res * a % mod;
	        a = a * a % mod;
	        k >>= 1;
	    }
	    return res;
	}
	void NTT(ll *a, int n, int type)
	{
	    for (int i = 0; i < n; ++i)
	        if (i < rev[i])
	            swap(a[i], a[rev[i]]);
	    for (int i = 1; i < n; i <<= 1)
	    {                       
	        ll gn = fast_power(type ? gg : gi, (mod - 1) / (i << 1));
	        for (int j = 0; j < n; j += (i << 1)) 
	        {
	            ll g0 = 1;
	            for (int k = 0; k < i; ++k, g0 = g0 * gn % mod)
	            {
	                ll x = a[j + k], y = g0 * a[i + j + k] % mod;
	                a[j + k] = (x + y) % mod;
	                a[i + j + k] = (x - y + mod) % mod;
	            }
	        }
	    }
	}
	void calc(int *aa,int *bb,int *c,int nn,int mm){
		memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(rev,0,sizeof(rev));
		n=nn;m=mm;
		for(int i=0;i<=n;i++)a[i]=aa[i];
		for(int i=0;i<=m;i++)b[i]=bb[i];
	    int len = 1 << max((int)ceil(log2(n + m)), 1ll); 
	    for (int i = 0; i < len; ++i) 
	        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (max((int)ceil(log2(n + m)), 1ll) - 1));
	    NTT(a, len, 1);
	    NTT(b, len, 1);
	    for (int i = 0; i <= len; ++i)
	        a[i] = a[i] * b[i] % mod; 
	    NTT(a, len, 0); 
	    ll inv = fast_power(len, mod - 2); 
	    for (int i = 0; i <= n + m; ++i)
		c[i]=a[i]*inv%mod; 
//	        printf("%lld ", a[i] * inv % mod);
//	    return 0;
	}
}NTT;
int mul1[1000006],mul2[100000 6];
signed main(){
//	 freopen("schrodingerstomb.in","r",stdin);
//	 freopen("schrodingerstomb.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0); 
	init();
	cin>>n>>m;
	f[1]=1;f[0]=1;
	for(int i=2;i<=n;i++)
	f[i]=C(i*2,i)*fm(i+1,mod-2)%mod;
	for(int i=m;i<=m;i++)
		for(int j=0;j<i;j++)
		u1[i-j-1]=C(i+j-1,i-1)*(i-j)%mod*fm(i,mod-2)%mod*inv[i-j-1]%mod;
	for(int i=n-m+1;i<=n-m+1;i++)
		for(int j=0;j<i;j++)
		u2[i-j-1]=C(i+j-1,i-1)*(i-j)%mod*fm(i,mod-2)%mod*inv[i-j-1]%mod;
	NTT.calc(u1,u2,w,n,n);
	for(int i=0;i<=n;i++)
	(w[i]*=jc[i])%=mod;
//	for(int i=0;i<=n;i++)
//		for(int j=0;j<=n;j++)
//		(w[i+j]+=u1[i+1]*u2[j+1]%mod*jc[i+j])%=mod;
	for(int i=1;i<=n;i++)
	(w[i]+=w[i-1])%=mod;
	memset(u1,0,sizeof(u1));
	memset(u2,0,sizeof(u2));
	for(int i=0;i<m;i++)u1[i]=f[i];
	for(int j=0;j<n-m+1;j++)u2[j]=f[j];
	NTT.calc(u1,u2,all,n,n);
//	for(int i=0;i<m;i++)
//		for(int j=0;j<n-m+1;j++)
//		all[i+j+1]+=f[i]*f[j]%mod;
	for(int len=2;len<=n;len++)
	(e[len]+=f[n-len]*all[len-1])%=mod;
	for(int i=n;i>=1;i--)
	(e[i]+=e[i+1])%=mod;
	for(int t=1;t<=n;t++){
		g[t]=(w[t-1])%mod;
		int del=0;
		g[t]=(g[t]-e[n-t+2]+mod)%mod;
	}
	for(int i=1;i<=n;i++)
	cout<<g[i]<<'\n';
	return 0;
}

详细

answer.code:81:30: error: expected ‘]’ before numeric constant
   81 | int mul1[1000006],mul2[100000 6];
      |                              ^~
      |                              ]