Codeforces Round #281 (Div. 2) E. Vasya and Polynomial

問題

多項式P(x)のうち、係数がすべて非負整数のものについて考える。すなわち、

P(x) =a_0 + a_1 * x + a_2 * x^2 + ... + a_n * x^n

としたとき、a_i>=0(0<=i<=n)となる。
３つの数t,a,bが与えられるので、P(t)=a, P(a)=bとなるような多項式P(x)の数を求めよ。

制約
1<=t,a,b<=10^18

解法

まず論外な場合（解が明らかに０になる場合）について考えます。
多項式が定数関数以外の場合、係数が全て正なのでP(x)>=xとなるはずです。
よって、

(a!=b and (t>a or a>b))

のときは答えが０です。

逆にa==bのときは、
定数関数P(x)=a
恒等関数（？）P(x)=x
の２通りが考えられ、答えはt==aのとき２、t!=aのとき１となります。
・・・と思っていると罠があって、t=a=b=1のときは
P(x)=x^n
が任意のnについて答えになるので、この時だけ答えが無限大になります。

同様の(t=1のときの)特殊ケースとして、
t=1
b=a^n(n>0)
というケースが挙げられます。この場合は
P(x)=a*x^(n-1)
が解となります。

それ以外の場合については、t,a,bの関係から多項式を明示的に求めることが出来ます。
http://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/
(Codeforcesのeditorialのコメント欄から拝借)

かいつまんで説明すると、
多項式P(x) =a_0 + a_1 * x + a_2 * x^2 + ... + a_n * x^n
に正の値を代入したとき、P(x)>=a_i(0<=i<=n)が成り立ちます。
ゆえにP(x)+1=Nとすると、

P(N)=a_0 + a_1 * N + a_2 * N^2 + ... + a_n * N^n

となり、これをNで割った余りがa_0となり、P(N)/NをNで割った余りがa_1となり、・・・
というように全ての係数を求めることができます。
（Nが十分大きくないとき、例えばN=1のときにはこの方法を使うことはできません、念のため）

というわけで、a>a_iが成り立つときは、
P(a)=bから多項式P(x)を導出し、P(t)=aが成り立つかを見てあげればよい、ということになります。
逆に言えばa>a_iと言い切れないケースがa==bの時（P(x)が定数関数の時）やt=1の時（P(x)=a*x^(n-1)やP(x)=x^nとなるとき）だったということになります。
あとはbを繰り返しaで割るという処理になりますので、a=1のときも特殊ケースとして対応します。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<ctime>
#include<set>
#include<bitset>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 100000000
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)		idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)	for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)		idp p2((x).F, (x).S)
#define dump(x,n)	idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)	idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)	idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)	idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)	rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)	rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;


bool chk(li t, li a, li b){
	vector<li> co;
	while(b>0){
		co.pb(b%a);
		b/=a;
	}
	li ta=0;
	rep(i,sz(co)){
		ta+=co[sz(co)-1-i];
		li taa=ta*t;
		if(i==sz(co)-1)return ta==a;
		if(taa/t!=ta)return false;
		ta=taa;
	}
	return ta/t==a;
}

int main(){
	li t,a,b;
	cin>>t>>a>>b;
	li res=0;
	if(t>1){
		if(t>a && a!=b){
			puts("0");
			return 0;
		}
		if(a==b){
			res++;
			if(t==a)res++;
		}
		else{
			if(a<b)res+=chk(t,a,b);
		}
		cout<<res<<endl;
	}
	else{
		if(max(a,b)==1)puts("inf");
		else if(a==1)puts("0");
		else{
			li bb=b;
			while(bb%a==0)bb/=a;
			if(bb==1 && b>1)puts("1");
			else cout<<chk(t,a,b)<<endl;
		}
	}
	


	return 0;
}

雑感
editorialを読んで時間をかけて考えればたしかに分かりますが、
そこそこ複雑で漏れを生みやすい場合分けゲーなので、ほとんどの場合でabからP(x)が計算できることに本番中に気付いたとしてもAC取れた気は全くしないですね・・・