QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#322569#5743. Palindromic PolynomialDaiRuiChen007WA 0ms4220kbC++173.0kb2024-02-07 11:14:052024-02-07 11:14:06

Judging History

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

  • [2024-02-07 11:14:06]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4220kb
  • [2024-02-07 11:14:05]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+5,MOD=1e9+9,i2=(MOD+1)/2,N=1e4;
ll ksm(ll a,ll b=MOD-2,ll p=MOD) {
	ll ret=1;
	for(;b;a=a*a%p,b=b>>1) if(b&1) ret=ret*a%p;
	return ret;
}
ll x[MAXN],y[MAXN],f[MAXN],g[MAXN],t[MAXN];
void solve() {
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(t,0,sizeof(t));
	int n,d=-1;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&x[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&y[i]);
	vector <array<ll,2>> pw_lims;
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) {
		if(x[i]*x[j]%MOD==1&&(y[i]||y[j])) {
			pw_lims.push_back({x[i],y[i]*ksm(y[j])%MOD});
		}
	}
	if(pw_lims.empty()) d=2*n;
	else {
		for(int i=N;~i;--i) {
			bool ok=1;
			for(auto&p:pw_lims) if(ksm(p[0],i)!=p[1]) ok=0;
			if(ok) { d=i; break; }
		}
		if(d==-1) return puts("-1"),void();
	}
	map <ll,ll> f_val;
	ll v0=0;
	for(int i=1;i<=n;++i) {
		if(!x[i]) v0=y[i];
		else {
			f_val[x[i]]=y[i];
			f_val[ksm(x[i])]=y[i]*ksm(x[i],MOD-1-d)%MOD;
		}
	}
	if(!v0) return puts("-1"),void();
	int len=0; f[0]=1;
	auto mul_poly=[&](ll k) {
//		printf("f *= x+%lld\n",k);
		++len;
		for(int i=len;i>=1;--i) f[i]=(f[i]*k+f[i-1])%MOD;
		f[0]=f[0]*k%MOD;
//		printf("get = "); for(int i=0;i<=len;++i) printf("%lld ",f[i]); puts(""); 
	};
	auto div_poly=[&](ll k) {
//		printf("f /= x+%lld\n",k);
		ll inv=ksm(k); f[0]=f[0]*inv%MOD;
		for(int i=1;i<=len;++i) f[i]=(f[i]+MOD-f[i-1])*inv%MOD;
		--len;
//		printf("get = "); for(int i=0;i<=len;++i) printf("%lld ",f[i]); puts(""); 
	};
	auto eval=[&](ll x) {
		ll y=0;
		for(int i=0;i<=d;++i) y=(y+ksm(x,i)*g[i])%MOD;
		return y;
	};
	vector <ll> fx,fy;
	int m=f_val.size();
	if(m-1>d) return puts("-1"),void();
	for(auto&p:f_val) fx.push_back(p.first),fy.push_back(p.second);
	for(int i=0;i<m;++i) mul_poly(MOD-fx[i]);
//	for(int i=0;i<m;++i) printf("exp f(%lld) = %lld\n",fx[i],fy[i]);
	for(int i=0;i<m;++i) {
		ll co=1;
		for(int j=0;j<m;++j) if(i!=j) {
			co=co*(fx[i]+MOD-fx[j])%MOD;
		}
		co=ksm(co)*fy[i]%MOD;
		div_poly(MOD-fx[i]);
		for(int j=0;j<=len;++j) g[j]=(g[j]+f[j]*co)%MOD;
		mul_poly(MOD-fx[i]);
//	for(int i=0;i<m;++i) printf("f(%lld) = %lld\n",fx[i],eval(fx[i])); puts("");
	}
//	for(int i=0;i<m;++i) printf("f(%lld) = %lld\n",fx[i],eval(fx[i])); puts("");
	for(int j=0;j<=d;++j) t[j]=g[j];
	for(int j=0;j<=d;++j) g[j]=(t[j]+t[d-j])*i2%MOD;
//	for(int i=0;i<m;++i) printf("f(%lld) = %lld\n",fx[i],eval(fx[i])); puts("");
	if(!g[0]||(v0&&g[0]!=v0)) {
		ll di=v0?(v0+MOD-g[0])%MOD:1;
		if(m>d) return puts("-1"),void();
		for(int j=0;j<=d;++j) t[j]=(f[j]+f[d-j])*i2%MOD;
		ll co=di*ksm(t[0])%MOD;
		for(int j=0;j<=d;++j) g[j]=(g[j]+co*t[j])%MOD;
//		for(int i=0;i<m;++i) printf("f(%lld) = %lld\n",fx[i],eval(fx[i])); puts("");
	}
	printf("%d\n",d);
	for(int i=0;i<=d;++i) printf("%lld ",g[i]);
	puts("");
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4220kb

input:

8
2
0 1
2 4
3
0 1 2
2 10 36
4
0 1 2 3
1 4 9 16
5
0 1 2 3 4
1 25 961 14641 116281
2
2 500000005
5 375000004
2
2 500000005
5 375000004
2
2 500000005
1 2
3
2 500000005 3
5 375000004 10

output:

4
2 0 0 0 2 
6
2 499999992 250000023 499999994 250000023 499999992 2 
8
1 219444442 747685194 447222236 171296285 447222236 747685194 219444442 1 
10
1 220932529 904208073 568307571 27339787 558424139 27339787 568307571 904208073 220932529 1 
-1
-1
-1
-1

result:

wrong answer Test case 5: there is a solution, but printed -1. (test case 5)