QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426358#8747. 朔望yanshanjiahongWA 1455ms141688kbC++143.1kb2024-05-31 08:46:512024-05-31 08:46:52

Judging History

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

  • [2024-05-31 08:46:52]
  • 评测
  • 测评结果:WA
  • 用时:1455ms
  • 内存:141688kb
  • [2024-05-31 08:46:51]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) x*2
#define rs(x) x*2+1
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second 
#define int long long
using namespace std;
typedef long long ll;
const int N=25,M=(1<<20)+5,mo=1e9+7,inf=1e9+7;
inline void read(int &p){
	int x=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int quick_power(int base,int x){
	int res=1;
	while(x){
		if(x&1)res*=base,res%=mo;
		base*=base,base%=mo;
		x>>=1;
	}
	return res;
}
int n,t[N],w[N];
struct divi{
	pii d[105];
	int cntd=0;
	friend divi operator+(divi x,divi y){
		divi res;
		rep(i,1,x.cntd){
			bool exi=0;
			rep(j,1,y.cntd){
				if(x.d[i].fir==y.d[j].fir)y.d[j].sec+=x.d[i].sec,exi=1;
				if(exi)break;
			}
			if(!exi)res.d[++res.cntd]=x.d[i];
		}
		rep(j,1,y.cntd)
		    res.d[++res.cntd]=y.d[j];
		sort(res.d+1,res.d+res.cntd+1);
		return res;
	}
}num[N],dif[N][N],dv[N][N];
divi getd(int x){
	divi res;
	rep(i,2,sqrt(x)){
		if(x<i)break;
		int cnt=0;
		while(x%i==0)
		    x/=i,cnt++;
		if(cnt)res.d[++res.cntd]=mp(i,cnt);
	}
	if(x!=1)res.d[++res.cntd]=(mp(x,1));
	return res;
}
int cntr;
divi getgcd(divi x,divi y){
	divi res;
	int nw=1;
	rep(i,1,x.cntd){
		while(nw<=y.cntd&&y.d[nw].fir<x.d[i].fir)
		    nw++;
		cntr++;
		if(y.d[nw].fir==x.d[i].fir)res.d[++res.cntd]=mp(x.d[i].fir,min(x.d[i].sec,y.d[nw].sec));
	}
	return res;
}
int cnts[M],tot;
int count(divi x){
	int res=1;
	rep(i,1,x.cntd)
	    res=res*quick_power(x.d[i].fir,x.d[i].sec)%mo;
	return res;
}
int dp[N][M];
signed main(){
//	freopen("P10548_1.in","r",stdin);
//	freopen("check.out","w",stdout);
	read(n),tot=(1<<n)-1;
	rep(i,1,n) 
	    read(t[i]);
	rep(i,2,n)
	    read(w[i]);
	rep(i,1,n)
	    num[i]=getd(t[i]);
	rep(i,1,n-1){
		rep(j,i+1,n){
			dif[i][j]=getd(t[j]-t[i]);
			rep(k,1,n)
			    if(i!=k&&j!=k)dv[i][j]=dv[i][j]+num[k];
			dv[i][j]=dv[i][j]+dif[i][j];
		}
	}
	rep(st,1,tot){
		if(__builtin_popcount(st)==1)continue;
		int fir=0;
		vector<divi>nwres[2];
		int op=0;
		rep(i,1,n){
			if(!((st>>(i-1))&1))continue;
			if(!fir)fir=i;
			else nwres[0].push_back(dv[fir][i]);
			while(nwres[op].size()>1){
				for(int j=0;j<(int)nwres[op].size();j+=2){
					if(j==(int)nwres[op].size()-1)nwres[op^1].push_back(nwres[op][j]);
					else nwres[op^1].push_back(getgcd(nwres[op][j],nwres[op][j+1])); 
				}
				nwres[op].clear(),op^=1;
			}
		}
		cnts[st]=2*count(nwres[op][0])%mo;
	}
	int ans=0,mult=1;
	rep(i,1,n)
	    mult*=t[i],mult%=mo;
	mult=quick_power(mult,mo-2);
	repp(st,tot,1){
		int nnum=__builtin_popcount(st);
		if(nnum==1)continue;
		rep(i,0,n){
			if(i&&(!((st>>(i-1))&1)))continue;
			rep(j,i+1,n){
				if((st>>(j-1))&1)continue;
				int nw=st|(1<<(j-1));
				dp[i][st]+=(dp[j][nw]+cnts[nw])%mo;
				dp[i][st]%=mo;
			}
		}
		cnts[st]=(cnts[st]-dp[0][st]+mo)%mo;
		ans+=w[nnum]*cnts[st]%mo*mult%mo;
		ans%=mo;
	}
	printf("%lld\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1455ms
memory: 141688kb

input:

20
73415948 190825288 205086969 242726140 280691039 291234110 341933576 379938879 399631744 420807939 421811250 486105558 605031352 645495854 714594262 775221445 793534057 818237037 926135349 940293639
108200337 125078426 163639475 261733041 280562529 287327830 310288774 415301468 419144734 46329977...

output:

394276441

result:

wrong answer 1st lines differ - expected: '153969420', found: '394276441'