#427585 (C) No.435 占い(Extra)

• 問題: No.435 占い(Extra)
• ユーザー: ciel
• 提出日時: 2020-02-09 00:25:07
• 言語: C (gcc 12.3.0)
• 結果: WA
• 実行時間: -
• コード長: 895 bytes
• コンパイル時間: 135 ms
• コンパイル使用メモリ: 32,896 KB
• 実行使用メモリ: 26,292 KB
• 最終ジャッジ日時: 2024-04-17 03:06:49
• 合計ジャッジ時間: 6,044 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	72 ms; 26,104 KB
testcase_01	AC	72 ms; 26,228 KB
testcase_02	AC	70 ms; 26,096 KB
testcase_03	AC	71 ms; 26,228 KB
testcase_04	AC	70 ms; 26,220 KB
testcase_05	AC	78 ms; 26,112 KB
testcase_06	AC	75 ms; 26,240 KB
testcase_07	AC	73 ms; 26,100 KB
testcase_08	AC	72 ms; 26,232 KB
testcase_09	AC	72 ms; 26,112 KB
testcase_10	WA	-
testcase_11	AC	80 ms; 26,112 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	AC	86 ms; 26,112 KB
testcase_15	AC	87 ms; 26,240 KB
testcase_16	AC	90 ms; 26,240 KB
testcase_17	AC	139 ms; 26,240 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	207 ms; 26,108 KB
testcase_24	AC	209 ms; 26,240 KB
testcase_25	AC	259 ms; 26,112 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	73 ms; 26,112 KB
testcase_29	WA	-
testcase_30	AC	207 ms; 26,112 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	204 ms; 26,112 KB
testcase_34	AC	228 ms; 26,112 KB
testcase_35	WA	-

ソースコード

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int I[]={-1,1,5,-1,7,2,-1,4,8};
unsigned char Fk[10000001];
short Fz[10000001];
int getFk(int i){
	return (Fk[i/2]>>i%2*4)&0xf;
}
void z(int n,int *n_,int *r_){
	int r=0;
	for(;n%3==0;n/=3)r++;
	*n_=n,*r_=r;
}
int comb(int n,int k){
	int k0=getFk(n),k1=getFk(k),k2=getFk(n-k);
	int z0=Fz[n],z1=Fz[k],z2=Fz[n-k];
	int z=z0-z1-z2,r=(int)k0*I[k1]*I[k2]%9;
	return z==0 ? r : z==1 ? r*3%9 : 0;
}
int main(){
	int i;
	Fk[0]=1,Fz[0]=0;
	for(i=1;i<=10000000;i++){
		int k0=getFk(i-1);
		int z0=Fz[i-1];
		int k1,z1;
		z(i,&k1,&z1);
		Fk[i/2]|=(k0*k1%9)<<i%2*4;
		Fz[i]=z0+z1;
	}
	int T,r;
	for(scanf("%d",&T),getchar();T--;){
		bool f=true;
		r=0;
		int n,x,a,b,m;
		scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);
		for(i=0;i<n;i++){
			int c=x%10;
			r=(r+c*comb(n-1,i))%9;
			if(c)f=false;
			x=((x^a)+b)%m;
		}
		printf("%d\n",r!=0||f ? r : 9);
	}
}