Codeforces #409 Div1 C. Vulnerable Kerbals

これは1500ptでもよい気がした。
http://codeforces.com/contest/800/problem/C

問題

整数Mと、M未満の異なる非負整数の集合が与えられる。
以下の条件を満たす数列を構成せよ。

• 各要素はM未満の非負整数である。
• 各prefixの積をMで割った互いに異なる値を取る。また、その数値は入力の集合に含まれない。
• 上記条件のうち最長である。

解法

途中0を並べてしまうと、以後はprefixの積がすべて0になるため、0を並べるなら末尾しかない。
さて、目的の数列Aを直接構成するのではなく、prefixの積を並べた数列Bを構成することを考える。
すなわち、B[i]=prod(A[0...i])となるBを作ろう。そうすればA[i]=B[i]/B[i-1]で結局Aも構成できる。

B[i]はB[i-1]に何か整数をかけてMの剰余を取った値であるため、G[i-1]=GCD(B[i-1],M)とするとB[i]はG[i-1]の倍数であれば任意の値を取れる。
そこで、0～(M-1)をMとのGCDでグループ分けしよう。
S(i) := GCD(x,M)=iとなるxの集合とする。

Bの要素として、S(i)内の要素の次には、S(i)内の別要素かS(j)の要素(jはiの倍数)を取ることができる。
よって、まずS(i)の要素を取り切ったうえで、以後より多くの要素を並べられそうなS(j)を取るようにしていくのが良い。
S(i)から遷移するのはiより大きなiの倍数jなので、DPでiの大きな順に遷移先を決めていけばよい。

A[i]=B[i]/B[i-1]の計算ではMが合成数の場合を考慮しよう。

int N,M;
int NG[202020];
vector<int> P[202020];
int ma[202020],to[202020];
int phi;

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hoge(ll a,ll b) {
	// b/a
	ll g=__gcd(a,b);
	a/=g;
	b/=g;
	ll ra=modpow(a,phi-1,M);
	return ra*b%M;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x, NG[x]=1;
		if(x==0) NG[M]=1;
	}
	for(i=1;i<=M;i++) if(__gcd(i,M)==1) phi++;
	
	for(i=M;i>=1;i--) if(M%i==0) {
		for(j=i;j<=M;j+=i) {
			if(NG[j]==0) {
				P[i].push_back(j);
				NG[j]=1;
			}
		}
		ma[i]=P[i].size();
		for(j=2*i;j<=M;j+=i) {
			int sc=P[i].size()+ma[j];
			if(sc>=ma[i]) {
				ma[i]=sc;
				to[i]=j;
			}
		}
	}
	
	vector<int> R;
	ll cur=1;
	ll tot=1;
	while(cur<=M) {
		FORR(r,P[cur]) {
			R.push_back(hoge(tot,r));
			tot=r;
		}
		if(cur==M) break;
		cur=to[cur];
	}
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r%M<<" ";
}

まとめ

結構面白い問題だと思いました。