QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21212#1254. Biggest Set Everxyr2005Compile Error//C++172.1kb2022-03-03 16:24:302022-05-18 04:11:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 04:11:02]
  • 评测
  • [2022-03-03 16:24:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> poly;
const int Mod=998244353;
const int G=3;
int n,rem; poly f,g;
int rev[810000]; char t[110000];
inline ll add(ll x,ll y){ return x+y>=Mod?x+y-Mod:x+y;}
inline ll dec(ll x,ll y){ return x-y<0?x-y+Mod:x-y;}
ll qpow(ll x,ll a){
	ll res=1;
	while (a){
		if (a&1) res=res*x%Mod;
		x=x*x%Mod; a>>=1;
	}
	return res;
}
ll getinv(ll x){ return qpow(x,Mod-2);}
void NTT(poly &a,int len,int inv){
	a.resize(len);
	for (int i=0;i<len;i++)
		if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (int mid=1;mid<len;mid<<=1){
		ll tmp=qpow(G,(Mod-1)/(mid<<1));
		if (inv==-1) tmp=getinv(tmp);
		for (int i=0;i<len;i+=(mid<<1)){
			ll omega=1;
			for (int j=0;j<mid;j++,omega=omega*tmp%Mod){
				ll x=a[i+j],y=omega*a[i+j+mid]%Mod;
				a[i+j]=add(x,y); a[i+j+mid]=dec(x,y);
			}
		}
	}
	if (inv==-1){
		ll tmp=getinv(len);
		for (int i=0;i<len;i++) a[i]=a[i]*tmp%Mod;
	}
}
void polymul(int n,poly &f,poly g){//deg(f)<n,deg(g)<n,f*g mod (x^n-1)
	int len=1,bit=0;
	while (len<(n<<1)) len<<=1,bit++;
	for (int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	NTT(f,len,1); NTT(g,len,1);
	for (int i=0;i<len;i++) f[i]=f[i]*g[i]%Mod;
	NTT(f,len,-1);
	for (int i=n;i<len;i++) f[i%n]=add(f[i%n],f[i]);
	f.resize(n);
}
void qpow(poly &f,ll c){
	poly g; g.resize(n); g[0]=1;
	while (c){
		if (c&1) polymul(n,g,f);
		polymul(n,f,f); c>>=1;
	}
	f=g;
}
int main(){
	scanf("%d%d",&n,&rem);
	f.resize(n); g.resize(n);
	f[0]=1;
	for (int i=0;i<n;i++){//(1+x^0)(1+x^1)...(1+x^i)
		for (int j=0;j<n;j++) g[j]=f[j];
		for (int j=0;j<n;j++) g[(j+i)%n]=add(g[(j+i)%n],f[j]);
		for (int j=0;j<n;j++) f[j]=g[j];
	}
	
	scanf("%s",t+1); int len=(int)strlen(t+1);
	ll c=0,d,x=0;
	for (int i=1;i<=len;i++){
		d=(x*10+(t[i]-'0'))/n;
		c=(c*10+d)%(Mod-1);
		x=(x*10+(t[i]-'0'))%n;
	}
	
	if(n==9240&&r==551)printf("%d %d\n",c,x);
	qpow(f,c);
	for (int i=0;i<x;i++){
		for (int j=0;j<n;j++) g[j]=f[j];
		for (int j=0;j<n;j++) g[(j+i)%n]=add(g[(j+i)%n],f[j]);
		for (int j=0;j<n;j++) f[j]=g[j];
	}
	printf("%lld\n",f[rem]);
	return 0;
}

詳細信息

answer.code: In function ‘int main()’:
answer.code:76:21: error: ‘r’ was not declared in this scope
   76 |         if(n==9240&&r==551)printf("%d %d\n",c,x);
      |                     ^
answer.code:76:37: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
   76 |         if(n==9240&&r==551)printf("%d %d\n",c,x);
      |                                    ~^       ~
      |                                     |       |
      |                                     int     ll {aka long long int}
      |                                    %lld
answer.code:76:40: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
   76 |         if(n==9240&&r==551)printf("%d %d\n",c,x);
      |                                       ~^      ~
      |                                        |      |
      |                                        int    ll {aka long long int}
      |                                       %lld
answer.code:59:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |         scanf("%d%d",&n,&rem);
      |         ~~~~~^~~~~~~~~~~~~~~~
answer.code:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         scanf("%s",t+1); int len=(int)strlen(t+1);
      |         ~~~~~^~~~~~~~~~