CF #354(Div2) E - The Last Fight Between Human and AI

問題 : Problem - 676E - Codeforces

概要 : n次多項式P(x)の係数を相手(AI?)と交互に決めて行って最終的にそれが(x-k)で割り切れたら人間の勝利。この問題では、その途中の段階での既に決まっている係数が与えられる。

解法 : まず、剰余の定理からP(k)=0になれば人間の勝利であることが分かる。
あとは、色々工夫して場合分けしたり、計算したりして判定する。実際P(k)の値を求めなくてはいけないのは全ての係数が決まってしまっている時だけ。

#include<iostream>
#include<string>
using namespace std;

const long long mod=1000000000000037;

long long a[100005];
long long x[100005];

int main(){
	int n,k;
	cin>>n>>k;
	int count=0;
	for(int i=0;i<=n;i++){
		string str;
		cin>>str;
		if(str=="?"){
			a[i]=mod;
			count++;
		}
		else a[i]=atoi(str.c_str());
	}

	if(k==0){
		if(a[0]==0){
			cout<<"Yes"<<endl;
		}
		else if(a[0]==mod){
			if((n-count)%2==0){
				cout<<"Yes"<<endl;
			}
			else cout<<"No"<<endl;
		}
		else cout<<"No"<<endl;
		return 0;
	}

	if(count>0){
		if(n%2)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		return 0;
	}
	long long sum=a[0];
	x[0]=1;
	for(int i=1;i<=n;i++){
		x[i]=(x[i-1]*k)%mod;
		sum=(sum+x[i]*a[i])%mod;
	}
	if(sum==0)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

反省 : k=0の時の場合分けに気付けなかった。mod=1000000007(有名な素数)では落ちるケースが用意されていた。結論modは素数でなくても十分に大きい数なら結局何でも良かった。ただ、この解法をとると適当なテストケースで落ちる可能性が少なからず残る。が、modを適当に何種類も試してどれでやっても全てP(k)=0となれば割りと正しいはず。P(k)が大きくなりすぎ得ることに対して、適当な素数での余りのP(k)%mod=0とするしか、能がなかった。