読者です 読者をやめる 読者になる 読者になる

Wolf Sotheとは?

決して暇ではないし、なんか節目の時期であるわけでもなく、Advent Calendarシーズンですらないのに、唐突に変な記事を書きます。

Wolf Sotheとは?

http://d.facdn.net/art/tozangezan/1489592891/1489592891.tozangezan_170315.png
昔のITMO Universityのアイスホッケーチームのユニフォーム。Edmonton Oilersと同じカラーリング。

このブログをわざわざ見ている人にはご存知かもしれませんが、Wolf Sotheというのは(特に僕がwriterをしているときによく登場する)プログラミングコンテストのキャラクターです。
例えば、以下のようなところに出没しています。
CODE FESTIVAL 2015 OKINAWA OPEN - CODE FESTIVAL 2015 OKINAWA OPEN | AtCoder
TopCoder Statistics - Match Overview SRM637 (non-tozangezanなWolf Sothe)
TopCoder Statistics - Problem Statement SRM690

本名は Tozan Southerpacks です。(pack: 狼の群れ) *1 現にプログラミングコンテスト上以外の彼(自分?)は、ほとんどTozanと呼ばれています。

いろいろあって彼はアイスホッケーが好きなんだそうです。

ちなみに、よくコンテストに持っていく狼のスモールマスコットはco-Sotheと言います。参考

おまけ

DCJが近いので本番で通せなかった問題を解いて振り返ったのでメモをば。

rps

これはまあ。使うノードの数を2のべきにする。ノードを使いすぎない。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include"rps.h"
using namespace std;

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
char ch[4200000];
long long ind[4200000];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetN();
	long long a=1LL<<N;
	int use=1;
	while(use*2<T&&use<a){
		use*=2;
	}
	if(I==T-1){
		for(int i=0;i<use;i++){
			Receive(i);
			ch[i]=GetChar(i);
			ind[i]=GetLL(i);
		}
		int n=use;
		while(n>1){
			int at=0;
			for(int i=0;i<n;i+=2){
				if((ch[i]=='R'&&ch[i+1]=='P')||(ch[i]=='S'&&ch[i+1]=='R')||(ch[i]=='P'&&ch[i+1]=='S')){
					ch[at]=ch[i+1];
					ind[at]=ind[i+1];
				}else{
					ch[at]=ch[i];
					ind[at]=ind[i];
				}
				at++;
			}
			n/=2;
		}
		printf("%lld\n",ind[0]);
	}else if(I<use){
		long long L=a/use*I;
		long long R=a/use*(I+1);
		for(long long i=L;i<R;i++){
			ch[i-L]=GetFavoriteMove(i);
			ind[i-L]=i;
		}
		int n=R-L;
		while(n>1){
			int at=0;
			for(int i=0;i<n;i+=2){
				if((ch[i]=='R'&&ch[i+1]=='P')||(ch[i]=='S'&&ch[i+1]=='R')||(ch[i]=='P'&&ch[i+1]=='S')){
					ch[at]=ch[i+1];
					ind[at]=ind[i+1];
				}else{
					ch[at]=ch[i];
					ind[at]=ind[i];
				}
				at++;
			}
			n/=2;
		}
		PutChar(T-1,ch[0]);
		PutLL(T-1,ind[0]);
		Send(T-1);
	}
}

necklace

2015finalの簡単枠。
substringのほうの文字列は短いことが大事。あとはここ1年で嫌という程見た「区間の左をiでスタートしたらどこまでいけるのか」をちまちま求めていく。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include"necklace.h"
using namespace std;

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
int str[10100000];
int in[3100];
int g[110][3100];
int sz[10100];
int q[10100][3010];
int to[3100];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNecklaceLength();
	int M=GetMessageLength();
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	for(int i=L;i<R;i++)str[i-L]=GetNecklaceElement(i);
	for(int i=0;i<M;i++)in[i]=GetMessageElement(i);
	for(int i=0;i<=M;i++){
		to[i]=i;
		if(i<M)q[in[i]][sz[in[i]]++]=i;
	}
	int n=R-L;
	for(int i=0;i<n;i++){
		int t=str[i];
		int ke=sz[t];
		for(int j=0;j<ke;j++){
			to[q[t][j]]++;
		}
		sz[t]=0;
		for(int j=0;j<ke;j++){
			if(to[q[t][j]]>=M)continue;
			q[in[to[q[t][j]]]][sz[in[to[q[t][j]]]]++]=q[t][j];
		}
	}
	if(I==0){
		for(int i=0;i<=M;i++)g[0][i]=to[i];
		for(int i=1;i<T;i++){
			Receive(i);
			for(int j=0;j<=M;j++)g[i][j]=GetInt(i);
		}
		int ret=0;
		for(int i=0;i<M;i++){
			int now=i;
			for(int j=0;j<T;j++){
				now=g[j][now];
			}
			ret=max(ret,now-i);
		}
		printf("%d\n",ret);
	}else{
		for(int i=0;i<=M;i++)PutInt(0,to[i]);
		Send(0);
	}
}

johnny

考察のほうが大事で、distribution要素はほぼない。
出次数が小さい順にソートして、左端から到達できる範囲の右端がどこかを探す。到達できない頂点がjohnnyの手札。
実は、転送するデータ量が結構厳しめ。一つ前のノードから受け取って一つ後のノードに転送すると、ノードあたりの通信量は抑えられるが、これは時間がかかるのでTLEする。
結局押し込むのが正解。charはsignedなので気をつける。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include"johnny.h"
using namespace std;

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
int out[21000];
pair<int,int> p[21000];
int at[21000];
int rev[21000];
int lm[21000];
bool is[210][21000];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=NumberOfCards();
	int L=N*I/T;
	int R=N*(I+1)/T;
	for(int i=L;i<R;i++){
		for(int j=0;j<N;j++){
			if(IsBetter(i,j)){
				out[i]++;
				is[i-L][j]=true;
			}
		}
	}
	if(I==0){
		for(int i=1;i<T;i++){
			int left=N*i/T;
			int right=N*(i+1)/T;
			Receive(i);
			for(int j=left;j<right;j++)out[j]=GetInt(i);
		}
		for(int i=0;i<N;i++)p[i]=make_pair(out[i],i);
		std::sort(p,p+N);
		for(int j=1;j<T;j++){
			for(int i=0;i<N;i++){
				PutChar(j,p[i].second/256);
				PutChar(j,p[i].second%256);
				at[i]=p[i].second;
			}
			Send(j);
		}
	}else{
		for(int i=L;i<R;i++)PutInt(0,out[i]);
		Send(0);
		Receive(0);
		for(int i=0;i<N;i++){
			at[i]=GetChar(0);
			if(at[i]<0)at[i]+=256;
			at[i]*=256;
			int tt=GetChar(0);
			if(tt<0)tt+=256;
			at[i]+=tt;
		}
		
	}
	for(int i=0;i<N;i++)lm[i]=rev[i];
	for(int i=0;i<N;i++)rev[at[i]]=i;
	for(int i=L;i<R;i++){
		for(int j=0;j<N;j++){
			if(is[i-L][j]){
				lm[i]=max(lm[i],rev[j]);
			}
		}
	}
	if(I==0){
		for(int i=1;i<T;i++){
			int left=N*i/T;
			int right=N*(i+1)/T;
			Receive(i);
			for(int j=left;j<right;j++)lm[j]=GetInt(i);
		}
		int tmp=0;
		for(int i=0;i<N;i++){
			if(tmp<i)break;
			tmp=max(tmp,lm[p[i].second]);
		}
		if(tmp==N-1)printf("IMPOSSIBLE\n");
		else printf("%d\n",N-tmp-1);
	}else{
		for(int i=L;i<R;i++)PutInt(0,lm[i]);
		Send(0);
	}
}

gold

2016final、2番目に簡単とはいえ、これが解ければ入賞できる。
基本アイデアは「範囲[L,R]が与えられた時、その中に金が埋まってるかを判定し、埋まってるならどこか一つの場所を返す」のをlogで求める方針。
両端の文字で場合分けすると2段階の処理で済むことになる。
特定の場所に偏りすぎだとあるノードで探す金の個数が多すぎるが、これはある程度多い時は諦め、再度親ノードに戻ってきて多かった場所をさらに分割してやり直せばよい。
打ち切りは何回くらいがいいのか多分真面目にやったら解析できるが、practiceにはlargeにフィードバックがあるのでサボった。

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<message.h>
#include"gold.h"
using namespace std;

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB
Send, Receive / 5 ~ 10ms?
Linear Message passing: slow (500ms through every nodes)

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
long long bs(long long L,long long R){
	while(1){
		long long M=(L+R)/2;
		char tmp=Search(M);
		if(tmp=='X')return M;
		if(L+1>=R)return -1;
		if(tmp!='>')R=M;
		else L=M+1;
	}
}
long long chk(long long L,long long R){
	if(L>=R)return -1;
	char Lc=Search(L);
	if(Lc=='X')return L;
	char Rc=Search(R-1);
	if(Rc=='X')return R-1;
	if(L+1==R)return -1;
	if(Lc!='<'&&Rc!='>'){
		return bs(L,R);
	}
	long long bl=L;
	long long br=R;
	if(Lc=='<'){
		long long ks=1;
		while(1){
			bl+=ks;
			ks*=2;
			if(bl>=R)break;
			char cc=Search(bl);
			if(cc=='X')return bl;
			if(cc!='<')break;
		}
	}
	if(Rc=='>'){
		long long ks=1;
		while(1){
			br-=ks;
			ks*=2;
			if(bl>=br)break;
			char cc=Search(br-1);
			if(cc=='X')return br-1;
			if(cc!='>')break;
		}
	}
	if(bl>=br)return -1;
	return bs(bl,br);
}
long long solve(long long L,long long R){
	long long ret=0;
	int cnt=0;
	queue<pair<long long,long long> > Q;
	Q.push(make_pair(L,R));
	while(Q.size()){
		pair<long long,long long> at=Q.front();Q.pop();
		if(at.first>=at.second)continue;
		long long tmp=chk(at.first,at.second);
		if(tmp>=0){
			cnt++;
			ret^=tmp;
			Q.push(make_pair(at.first,tmp));
			Q.push(make_pair(tmp+1,at.second));
		}
		if(cnt==10000)break;
	}
	if(cnt==10000){
		return -1;
	}
	return ret;
}
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=NumberOfNuggets();
	long long L=RoadLength();
	//printf("%d\n",I);
	if(I==T-1){
		vector<pair<long long,long long > >Q[10];
		long long ret=0;
		Q[0].push_back(make_pair(0,L));
		for(int i=0;i<9;i++){
			for(int j=0;j<Q[i].size();j++){
				long long n=Q[i][j].second-Q[i][j].first;
				for(int k=0;k<T-1;k++){
					long long left=Q[i][j].first+n*k/(T-1);
					long long right=Q[i][j].first+n*(k+1)/(T-1);
					PutLL(k,left);
					PutLL(k,right);
				}
			}
			for(int j=0;j<T-1;j++){
				PutLL(j,-1);
				PutLL(j,-1);
				Send(j);
			}
			for(int j=0;j<T-1;j++){
				Receive(j);
				for(int k=0;k<Q[i].size();k++){
					long long tmp=GetLL(j);
					if(tmp<0){
						long long n=Q[i][k].second-Q[i][k].first;
						long long left=Q[i][k].first+n*j/(T-1);
						long long right=Q[i][k].first+n*(j+1)/(T-1);
						if(left<right){
							Q[i+1].push_back(make_pair(left,right));
						}
					}else ret^=tmp;
				}
				GetLL(j);
			}
		}
		printf("%lld\n",ret);
	}else{
		for(int i=0;i<9;i++){
			Receive(T-1);
			while(1){
				long long left=GetLL(T-1);
				long long right=GetLL(T-1);
				if(left<0)break;
				
				long long ret=solve(left,right);
		//		printf("%lld %lld: %lld\n",left,right,ret);
				PutLL(T-1,ret);
			}
			PutLL(T-1,-1);
			Send(T-1);
		}
	}
}

*1: どうでもいいんですけど、"souther"という単語は発音がsάʊðɚなのに対し"southerly"という単語はsˈʌðɚliになったりします。Southerpacksはどう読むのか僕にもいまいちよくわかりませんが、英語圏の人はsˈʌðɚpæksと呼んでいるような気がします。だからWolf Sotheも似たような発音で読むのです(投げやり)

SRM186 Div1 Hard

昔の問題は変な意味で面白い。

プログラミングコンテストの問題の題材としてアイスホッケーが出題されることは少なくありません.しかし,活動時間の全てをオンラインジャッジにつぎ込む生活では,アイスホッケーを想像することができず,問題の理解に困ってしまうこともあるでしょう.一分一秒を争うこの世界では,致命傷となりかねません.

当然この問題の本質は問題文読解なんだけど、まず普通の人が思い浮かべるのは、「好きな方向に打てて何回でも反射できるので最短距離を求める」みたいな感じ。しかしテストケースを見てみても問題の妥当性を考えてみてもこれはおかしいので、徐々に「反射は1回以下なのでは...?」と疑うことになる。
それでもなおうまくいかないので、魔力で反射が0回のケースは考慮してはいけないことと、問題文冒頭の The left-handed Finnish hockey player から左利き選手は右にシュートしやすそうだから右のみ反射なのでは?と考えるに至る。

実は、画像の下の段落にちょろっと反射のルールが書いてあるんだけど、実はここでは「right」としか書いてない上実はこれは反射の法則ではなく、この問題でvalidとみなされる移動の仕方である。知るか。

複数経路があるときの処理も謎でゴールの右端に近いものを採用するんだけど(角度のminではない)、これも実際ゴールを入れる人は端に打ってそうだなあと思うとなんか納得できなくもない感じになる。これらのエスパーによって同点のものがたくさん現れてどれを出力しないといけないか問題も解消できて一件落着。


冒頭みたいな逸話は笑い話のように扱われていますが、この「アイスホッケー」を「物理学」や「機械・パソコンの仕組み」に置き換えてみると、未だに背景知識がないと理解できない系の問題文を書く人がいます。専門的なストーリーにしたいときはちゃんと親切に全部問題文中に記述されているかどうかを念入りに確認しましょう。物体の落下の仕方の式やファイルのURLの表し方に説明がないなんて論外です。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const double EPS = 1e-13;
const double INF = 1e+10;
const double PI = acos(-1);
vector<Pt>L;
vector<Pt>R;
vector<Pt>hb;
class PuckShot {
	public:
	double caromAngle(int X0, vector <int> X, vector <int> Y) {
		int n=X.size();
		double val=INF;
		double ret=-1.0;
		hb.push_back(Pt(X0,1));
		for(int i=0;i<=1;i++){
			for(int j=0;j<n;j++){
				double tx=X[j];
				double ty=Y[j];
				if(i%2==0)tx+=3000*i;
				else{
					tx=3000-tx;
					tx+=3000*i;
				}
				L.push_back(Pt(tx-25,ty));
				R.push_back(Pt(tx+25,ty));
				hb.push_back(Pt(tx-25-(1e-10),ty));
				hb.push_back(Pt(tx+25+(1e-10),ty));
			}
			if(i==0)continue;
			Pt gl,gr;
			gl=Pt(3000*i+1408.5,1733);
			gr=Pt(3000*i+1591.5,1733);
			if(i%2)swap(gl,gr);
			hb.push_back(gl);
			hb.push_back(gr);
			for(int j=0;j<hb.size();j++){
				bool ok=true;
				for(int k=0;k<L.size();k++){
					if(iLS(Pt(X0,0),hb[j],L[k],R[k])){
						ok=false;break;
					}
				}
				if(!iLS(Pt(X0,0),hb[j],gl,gr))ok=false;
				if(ok){
					Pt p=pLL(Pt(X0,0),hb[j],gl,gr);
					double dist=(p-gr).ABS();
		//			printf("%f %f %f\n",hb[j].x,hb[j].y,dist);
					if(dist<val){
						val=dist;
						ret=(hb[j]-Pt(X0,0)).arg()*180/PI;
					}
				}
			}
		}
		return ret;
	}
};

最大独立集合 速め

696Mediumで書いたもの。38頂点を1000回実行して200ms弱と相当速い。
s[i][j]: 隣接行列
S[i]: 隣接行列を詰め込んだもの
v[i]: 頂点の利用状況
val: 答え
uk: v[i]=0のiを詰め込んだもの
n: 頂点数

int s[40][40];
long long S[40];
int v[40];
int val;
int n;
long long uk=0;
void calc(){
	int nm=0;
	for(int i=0;i<n;i++)if(v[i]==1)nm++;
	val=max(val,nm);
	for(int i=0;i<n;i++){
		if(v[i]==0&&__builtin_popcountll(uk&S[i])<2){
			v[i]=1;
			uk-=1LL<<i;
			long long ch=0;
			for(int j=0;j<n;j++)if(v[j]==0&&s[i][j]){v[j]=2;ch+=1LL<<j;uk-=1LL<<j;}
			calc();
			v[i]=0;
			uk+=1LL<<i;
			for(int j=0;j<n;j++)if(ch&(1LL<<j)){v[j]=0;uk+=1LL<<j;}
			return;
		}
	}
	int dm=1;
	int at=-1;
	for(int i=0;i<n;i++){
		if(v[i]==0&&__builtin_popcountll(uk&S[i])>=dm){
			dm=__builtin_popcountll(uk&S[i]);
			at=i;
		}
	}
	if(at==-1)return;
	v[at]=2;
	uk-=1LL<<at;
	calc();
	v[at]=0;
	uk+=1LL<<at;
	
	v[at]=1;
	uk-=1LL<<at;
	long long ch=0;
	for(int j=0;j<n;j++){
		if(v[j]==0&&s[at][j]){
			v[j]=2;
			uk-=1LL<<j;
			ch+=(1LL<<j);
		}
	}
	calc();
	for(int j=0;j<n;j++){
		if(ch&1LL<<j){v[j]=0;uk+=1LL<<j;}
	}
	v[at]=0;uk+=1LL<<at;
}

698F: Coprime Permutation

素因数→素因数の写像が何通りあるかと、それぞれの素因数内で数の並べ方が何通りあるか掛け算する。
前者は、同じ回数出現する素因数が自由に入れ替えられるので、それぞれの素因数に対して、indexにその素因数をもつ場所のgcdを求めて、対応をつけると自由度がわかので階乗をかける。
後者は、(素因数の集合)ごとに独立で、これも前計算してから同様に自由度を求めて階乗をかける。

でも証明はできていない。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[1100000];
int pr[1100000];
int st[1100000];
int to[1100000];
int val[1100000];
int wk[1100000];
int tk[1100000];
long long fact[1100000];
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
int pl[110000];
int dec[1100000];
int used[1100000];
vector<int> pp[1100000];
int main(){
	int a;scanf("%d",&a);
	fact[0]=1;
	for(int i=1;i<1100000;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	pr[0]=pr[1]=-1;
	for(int i=2;i<1100000;i++){
		if(pr[i]==-1)continue;
		pr[i]=1;
		for(int j=i+i;j<1100000;j+=i)pr[j]=-1;
	}
	st[1]++;
	for(int i=2;i<=a;i++){
		if(pr[i]==1){
			st[a/i]++;
			for(int j=i;j<=a;j+=i)pp[j].push_back(i);
		}
	}
	int ind=0;
	for(int i=2;i<1100000;i++){
		if(pr[i]==1)pl[ind++]=i;
	}
	long long ret=1;
	if(pr[b[0]]==1||b[0]==1){
		used[b[0]]=1;
		dec[1]++;
	}
	for(int i=1;i<=a;i++){
		if(pr[i]==1){
			int now=0;
			for(int j=i;j<=a;j+=i){
				if(!b[j-1])continue;
				now=gcd(now,b[j-1]);
			}
			if(now!=0){
				bool ok=false;
				int ss=-1;
				for(int j=0;j<pp[now].size();j++){
					if(a/pp[now][j]==a/i){
						ss=pp[now][j];
						ok=true;break;
					}
				}
				if(!ok&&a/i==1&&now==1){
					ss=now;
					ok=true;
				}
			//	printf("%d: %d %d\n",i,now,ss);
				if(used[ss]||!ok){

					printf("0\n");return 0;
				}
				used[ss]=1;
				dec[a/i]++;
			}
		}
	}
	for(int i=1;i<=a;i++)ret=ret*fact[st[i]-dec[i]]%mod;
	for(int i=1;i<=a;i++)val[i]=1;
	for(int i=2;i<=a;i++){
		if(pr[i]==1){
			for(int j=i;j<=a;j+=i)val[j]*=i;
		}
	}
	for(int i=1;i<=a;i++)wk[val[i]]++;
	for(int i=0;i<a;i++){
		if(b[i])tk[val[b[i]]]++;
	}
	for(int i=1;i<=a;i++)ret=ret*fact[wk[i]-tk[i]]%mod;
	printf("%I64d\n",ret);
}

Codeforces Round #348 (VK Cup 2016 Round 2, Div. 1 Edition)

何だこのセットは......。難問が誰にも存在しないセットだと、簡単が速いから勝ててしまう。

A B C D E F Place
00:13 00:06 00:34 (+1) 00:48 - - 4th

A:
逆からやるだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[11000][4];
int mat[110][110];
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		scanf("%d%d",&p[i][0],&p[i][1]);
		p[i][1]--;
		if(p[i][0]==3){
			scanf("%d%d",&p[i][2],&p[i][3]);
			p[i][2]--;
		}
	}
	for(int i=c-1;i>=0;i--){
		if(p[i][0]==3){
			mat[p[i][1]][p[i][2]]=p[i][3];
		}else if(p[i][0]==2){
			int tmp=mat[a-1][p[i][1]];
			for(int j=a-1;j>0;j--){
				mat[j][p[i][1]]=mat[j-1][p[i][1]];
			}
			mat[0][p[i][1]]=tmp;
		}else{
			int tmp=mat[p[i][1]][b-1];
			for(int j=b-1;j>0;j--){
				mat[p[i][1]][j]=mat[p[i][1]][j-1];
			}
			mat[p[i][1]][0]=tmp;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(j)printf(" ");
			printf("%d",mat[i][j]);
		}
		printf("\n");
	}
}

B:
偶奇ごとに持っておけば、偶数奇数それぞれの中では平行移動してるだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int ret[1100000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int p1=0;
	int p2=1;
	while(b--){
		int c;scanf("%d",&c);
		if(c==1){
			int d;scanf("%d",&d);
			p1+=d;
			p2+=d;
			if(p1<0)p1+=a;
			if(p2<0)p2+=a;
			if(p1>=a)p1-=a;
			if(p2>=a)p2-=a;
			
		}else{
			p1^=1;
			p2^=1;
		}
	}
	for(int i=0;i<a/2;i++){
		ret[(p1+i*2)%a]=i*2+1;
		ret[(p2+i*2)%a]=i*2+2;
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ret[i]);
	}
	printf("\n");
}

C:
手元で二次方程式を解く・sqrtの中身を負にしないように

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
double A[110000];
double B[110000];

double x[110000];
double y[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%lf",A+i);
	for(int i=0;i<a;i++)scanf("%lf",B+i);
	double p1=0;
	double p2=0;
	for(int i=0;i<a;i++)p2+=B[i];
	for(int i=0;i<a-1;i++){
		p1+=A[i];
		p2-=B[i];
		y[i]=0.5*((p1-p2+1)+sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1)));
		x[i]=0.5*((p1-p2+1)-sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1)));
	}
	x[a-1]=y[a-1]=1;
	for(int i=a-1;i>0;i--){
		x[i]-=x[i-1];
		y[i]-=y[i-1];
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",x[i]);
	}
	printf("\n");
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",y[i]);
	}
	printf("\n");
	
}

D:
追加する数ごとに独立で、内部でも座標圧縮してBITするだけ...。残り2問と比べてあまりにも簡単すぎる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int x[110000];
int b[110000];
int t[110000];
int z[110000];
vector<int>q[110000];
int bit[110000];
int sz;
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<sz;a|=a+1)bit[a]+=b;
}
int z2[110000];
int ans[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",b+i,t+i,x+i);
		z[i]=x[i];
	}
	std::sort(z,z+a);
	for(int i=0;i<a;i++){
		int at=lower_bound(z,z+a,x[i])-z;
		q[at].push_back(i);
	}
	for(int i=0;i<a;i++){
		if(q[i].size()){
			sz=q[i].size();
			for(int j=0;j<q[i].size();j++){
				z2[j]=t[q[i][j]];
			}
			std::sort(z2,z2+sz);
			for(int j=0;j<q[i].size();j++){
				int ind=lower_bound(z2,z2+sz,t[q[i][j]])-z2;
				if(b[q[i][j]]==1){
					add(ind,1);
				}else if(b[q[i][j]]==2){
					add(ind,-1);
				}else{
					ans[q[i][j]]=sum(0,ind);
				}
			}
			for(int j=0;j<sz;j++)bit[j]=0;
		}
	}
	for(int i=0;i<a;i++){
		if(b[i]!=3)continue;
		printf("%d\n",ans[i]);
	}
}

F:
虚無。
Black box linear algebraを勉強する(これも虚無)か、虚無を実装するか。木分解でもうまくいきそうに見えるけどどうなんだこれ。

第3回 Dwangoからの挑戦状 Finals

えええ....。せっかくの優勝チャンスを逃した。

A B C D Place
118:47 70:40 (+2) 47:52 (+2) - 5th

A:
ずっと前から見てて解けないと思ってトイレにいったら後ろからやるだけだった。こういうのが遅いのはダメでしょ

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[100];
int dp[60][60][60][2];
int v[60][60][60];
void solve(int a,int b,int c){
	if(v[a][b][c])return ;
	v[a][b][c]=1;
	// +
 
	dp[a][b][c][0]=-mod;
	dp[a][b][c][1]=mod;
	int rem=c;
	if(in[b]!='+')rem--;
	for(int i=a;i<b;i++){
		for(int j=0;j<=rem;j++){
			solve(a,i,j);
			solve(i+1,b-1,rem-j);
			if(dp[a][i][j][0]>-mod&&dp[i+1][b-1][rem-j][0]>-mod){
				dp[a][b][c][0]=max(dp[a][i][j][0]+dp[i+1][b-1][rem-j][0],dp[a][b][c][0]);
				dp[a][b][c][1]=min(dp[a][i][j][1]+dp[i+1][b-1][rem-j][1],dp[a][b][c][1]);	
			}
		}
	}
	// -
	rem=c;
	if(in[b]!='-')rem--;
	for(int i=a;i<b;i++){
		for(int j=0;j<=rem;j++){
			solve(a,i,j);
			solve(i+1,b-1,rem-j);
			if(dp[a][i][j][0]>-mod&&dp[i+1][b-1][rem-j][0]>-mod){
				dp[a][b][c][0]=max(dp[a][i][j][0]-dp[i+1][b-1][rem-j][1],dp[a][b][c][0]);
				dp[a][b][c][1]=min(dp[a][i][j][1]-dp[i+1][b-1][rem-j][0],dp[a][b][c][1]);	
			}
		}
	}
	if(a==b){
		if(c){
			dp[a][b][c][0]=max(dp[a][b][c][0],9);
			dp[a][b][c][1]=min(dp[a][b][c][1],0);
			
		}
		if('0'<=in[a]&&in[a]<='9'){
			dp[a][b][c][0]=max(dp[a][b][c][0],in[a]-'0');
			dp[a][b][c][1]=min(dp[a][b][c][1],in[a]-'0');
		}
	}
}
int main(){
	int a;scanf("%d%s",&a,in);
	int n=strlen(in);
	solve(0,n-1,a);
	if(dp[0][n-1][a][0]==-mod){
		printf("NG\n");return 0;
	}else printf("OK\n%d\n",dp[0][n-1][a][0]);
}

B:
はじめてのMo。速くできるのはわかるけども、速くしなくても定数倍で1/2くらいの割合の人が通るみたいなのは、経験のあるwriterがやるはずないですよね。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int si[11000];
 
int v[110000];
vector<pair<int,int> >ss[110000];
long long ret=1;
long long inv[2200000];
long long ans[110000];
int SQ=300;
vector<pair<pair<int,int>,int> > ev[350]; // rm, lm, id
int main(){
 
	int a,b;scanf("%d%d",&a,&b);
	inv[1]=1;
	for(int i=2;i<2200000;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=0;i<a;i++){
		int p;scanf("%d",&p);
		for(int j=2;j*j<=p;j++){
			if(p%j==0){
				int cur=0;
				while(p%j==0){
					p/=j;cur++;
				}
				ss[i].push_back(make_pair(j,cur));
				v[j]=1;
			}
		}
		if(p>1){
			v[p]=1;
			ss[i].push_back(make_pair(p,1));
		}
	}
	int sz=0;
	for(int i=0;i<110000;i++){
		if(v[i])v[i]=sz++;
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;
		ev[p/SQ].push_back(make_pair(make_pair(q,p),i));
	}
	for(int i=0;i<350;i++){
		std::sort(ev[i].begin(),ev[i].end());
	}
	for(int i=0;i<350;i++){
		int l=i*SQ;
		int r=i*SQ;
		for(int j=0;j<sz;j++)si[j]=1;
		ret=1;
		for(int j=0;j<ev[i].size();j++){
			int p=ev[i][j].first.second;
			int q=ev[i][j].first.first;
			int id=ev[i][j].second;
			if(r<q){
				while(r<q){
					for(int k=0;k<ss[r].size();k++){
						int to=ss[r][k].first;
						int am=ss[r][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					r++;
				}
			}
			if(l>p){
				while(l>p){
					for(int k=0;k<ss[l-1].size();k++){
						int to=ss[l-1][k].first;
						int am=ss[l-1][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					l--;
				}
			}
			if(r>q){
				while(r>q){
					r--;
					for(int k=0;k<ss[r].size();k++){
						int to=ss[r][k].first;
						int am=-ss[r][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
				}
			}
			if(l<p){
				while(l<p){
					for(int k=0;k<ss[l].size();k++){
						int to=ss[l][k].first;
						int am=-ss[l][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					l++;
				}
			}
			ans[id]=ret;
		}
	}
	for(int i=0;i<b;i++)printf("%lld\n",ans[i]);
}

C:
点を含む丸を121回で見つけたら、丸をどのくらい上に動かしても大丈夫か、どのくらい右に動かしても大丈夫かを二分探索で求めて。円の交点のどっちか1つが答え。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[110];
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline double ABS(double a){return max(a,-a);}
struct Pt {
	double x, y;
	Pt() {}
	Pt(double x, double y) : x(x), y(y) {}
	Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
	Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
	Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
	Pt operator-() const { return Pt(-x, -y); }
	Pt operator*(const double &k) const { return Pt(x * k, y * k); }
	Pt operator/(const double &k) const { return Pt(x / k, y / k); }
	double ABS() const { return sqrt(x * x + y * y); }
	double abs2() const { return x * x + y * y; }
	double arg() const { return atan2(y, x); }
	double dot(const Pt &a) const { return x * a.x + y * a.y; }
	double det(const Pt &a) const { return x * a.y - y * a.x; }
};
double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
pair<Pt,Pt> pCC(Pt a, double r, Pt b, double s) {
	double d = (b - a).ABS();
	double x = (d * d + r * r - s * s) / (d * 2);
	Pt e = (b - a) / d, w = e * Pt(0, 1) * sqrt(max(r * r - x * x, 0.0));
	return make_pair(a + e * x - w, a + e * x + w);
}
Pt c;
int main(){
	bool ok=false;
	for(int i=0;i<=10;i++){
		if(ok)break;
		for(int j=0;j<=10;j++){
			if(ok)break;
			printf("%d %d\n",i*100000,j*100000);fflush(stdout);
			scanf("%s",in);
			if(in[1]=='o')return 0;
			if(in[1]=='l'){
				ok=true;
				c=Pt(i*100000,j*100000);
			}
		}
	}
	double left=0;
	double right=200000;
	for(int i=0;i<35;i++){
		double M=(left+right)/2;
		printf("%.12f %.12f\n",c.x+M,c.y);
		fflush(stdout);
		scanf("%s",in);
		if(in[1]=='o')return 0;
		if(in[1]=='l')left=M;
		else right=M;
	}
	double X=c.x+left;
	left=0;
	right=200000;
	for(int i=0;i<35;i++){
		double M=(left+right)/2;
		printf("%.12f %.12f\n",c.x,c.y+M);
		fflush(stdout);
		scanf("%s",in);
		if(in[1]=='o')return 0;
		if(in[1]=='l')left=M;
		else right=M;
	}
	double Y=c.y+left;
	pair<Pt,Pt> tt=pCC(Pt(X,c.y),100000,Pt(c.x,Y),100000);
	int t1=tt.first.x-0.5;
	int t2=tt.first.y-0.5;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		printf("%d %d\n",t1+i,t2+j);fflush(stdout);scanf("%s",in);
		if(in[1]=='o')return 0;
	}
	t1=tt.second.x-0.5;
	t2=tt.second.y-0.5;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		printf("%d %d\n",t1+i,t2+j);fflush(stdout);scanf("%s",in);
		if(in[1]=='o')return 0;
	}
}

D:
どうみても遅延更新segtreeであることはわかるしだいたいこういうことがしたいというのはわかるけども、能力が至らず解けなかった。こういう負け方(敗因が練習不足であるのがはっきりしてるケース)が一番ダメ。

Codeforces Round #349 (Div. 1)

いつもと同じ死に方。成長が見られない。相変わらず注意力が灰底辺。

A B C D E Place
00:48 (+1) 00:35 (+4) 01:59 (+1) - - 59th

A:
メモ化再帰するだけ。メモ化し忘れて1TLE。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[11000];
int dp[11000][3];
set<string>S;
char tmp[4];
int n;
int solve(int a,int b){
	if(~dp[a][b])return dp[a][b];
	if(a==n)return dp[a][b]=1;
	int t=0;
	if(a<=n-2){
		if(b!=0||in[a]!=in[a-2]||in[a+1]!=in[a-1]){
			int res=solve(a+2,0);
			if(res){
				t=res;
				tmp[2]=0;tmp[0]=in[a];tmp[1]=in[a+1];string tt=tmp;S.insert(tt);
			}
		}	
	}
	if(a<=n-3){
		if(b!=1||in[a]!=in[a-3]||in[a+1]!=in[a-2]||in[a+2]!=in[a-1]){
			int res=solve(a+3,1);
			if(res){
				t=res;
				tmp[3]=0;tmp[0]=in[a];tmp[1]=in[a+1];tmp[2]=in[a+2];string tt=tmp;S.insert(tt);
			}
		}	
	}
	return dp[a][b]=t;
}
int main(){
	scanf("%s",in);
	n=strlen(in);
	for(int i=0;i<11000;i++)for(int j=0;j<3;j++)
		dp[i][j]=-1;
	for(int i=5;i<=n;i++){
		solve(i,2);
	}
	printf("%d\n",(int)(S.size()));
	for(set<string>::iterator it=S.begin();it!=S.end();it++)printf("%s\n",(*it).c_str());
}

B:
なにも変な要素がないのにひたすらWA。頭が悪すぎる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[3100];
int dist[3100][3100];
int L[3100][3];
int R[3100][3];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)dist[i][j]=-1;
		queue<int>Q;
		Q.push(i);
		dist[i][i]=0;
		while(Q.size()){
			int at=Q.front();Q.pop();
			for(int j=0;j<g[at].size();j++){
				int to=g[at][j];
				if(dist[i][to]==-1){
					dist[i][to]=dist[i][at]+1;
					Q.push(to);
				}
			}
		}
	}
	for(int i=0;i<a;i++){
		L[i][0]=L[i][1]=L[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[j][i]==-1)continue;
			if(L[i][0]==-1||dist[j][i]>dist[L[i][0]][i]){
				L[i][2]=L[i][1];
				L[i][1]=L[i][0];
				L[i][0]=j;
			}else if(L[i][1]==-1||dist[j][i]>dist[L[i][1]][i]){
				L[i][2]=L[i][1];
				L[i][1]=j;
			}else if(L[i][2]==-1||dist[j][i]>dist[L[i][2]][i]){
				L[i][2]=j;
			}
		}
	}
	for(int i=0;i<a;i++){
		R[i][0]=R[i][1]=R[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[i][j]==-1)continue;
			if(R[i][0]==-1||dist[i][j]>dist[i][R[i][0]]){
				R[i][2]=R[i][1];
				R[i][1]=R[i][0];
				R[i][0]=j;
			}else if(R[i][1]==-1||dist[i][j]>dist[i][R[i][1]]){
				R[i][2]=R[i][1];
				R[i][1]=j;
			}else if(R[i][2]==-1||dist[i][j]>dist[i][R[i][2]]){
				R[i][2]=j;
			}
		}
	}
	int A,B,C,D;
	int bs=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<3;k++)for(int l=0;l<3;l++){
				if(L[i][k]==-1||R[j][l]==-1||dist[i][j]==-1)continue;
				if(i==j||i==R[j][l]||j==L[i][k]||L[i][k]==R[j][l])continue;
				if(bs<dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]]){
					bs=dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]];
					A=L[i][k];B=i;C=j;D=R[j][l];
				}
			}
		}
	}
	set<int>S;
	S.insert(A);
	S.insert(B);
	S.insert(C);
	S.insert(D);
	if(S.size()!=4){
		while(1);
	}
	printf("%d %d %d %d\n",A+1,B+1,C+1,D+1);
}

C:
nCkテーブルをsqrt(N)段ごとに作っておいて一行ずつ下がるやつに係数をつけただけ。一箇所-1し忘れ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[110000];
int n;
int sz=0;
pair<pair<int,int>,int>p[110000];
int ans[110000];
int SQ=300;
long long fact[110000];
long long inv[110000];
long long finv[110000];
long long C(int a,int b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
long long val[110000];
long long sum[110000];
long long p26[110000];
long long p25[110000];
int main(){
	fact[0]=finv[0]=1;
	p26[0]=1;
	p25[0]=1;
	inv[1]=1;
	for(int i=2;i<110000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<110000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
		p26[i]=p26[i-1]*26%mod;
		p25[i]=p25[i-1]*25%mod;
	}
	int a;scanf("%d",&a);
	scanf("%s",in);
	n=strlen(in);
	while(a--){
		int t;scanf("%d",&t);
		if(t==1){
			scanf("%s",in);
			n=strlen(in);
		}else{
			int b;scanf("%d",&b);
			p[sz]=make_pair(make_pair(b,n),sz);
			sz++;
		}
	}
	std::sort(p,p+sz);
	int at=0;
	for(int i=0;i<340;i++){
		long long ks=1;
		for(int j=i*SQ;j>=0;j--){
			val[j]=C(i*SQ,j)*ks;
			ks=ks*25%mod;
		}
		for(int j=0;j<=i*SQ;j++){
			sum[j]=val[j];
			if(j)sum[j]=(sum[j]+sum[j-1])%mod;
		}
		while(at<sz&&p[at].first.first<(i+1)*SQ){

			if(p[at].first.first<p[at].first.second){
				at++;continue;
			}
			long long now=sum[min(i*SQ,p[at].first.second-1)];

			int r=min(i*SQ,p[at].first.second-1);
			for(int j=0;j<p[at].first.first%SQ;j++){
				if(r==p[at].first.second-1){
					now=now*26%mod;
					now=(now+mod-C(i*SQ+j,r)*p25[i*SQ+j-r]%mod)%mod;
				}else{
					now=now*26%mod;
					r++;
				}
			}

			ans[p[at].second]=(p26[p[at].first.first]+mod-now)%mod;
			at++;
		}
	}
	for(int i=0;i<sz;i++)printf("%d\n",ans[i]);
}