yukicoder No.391 CODING WAR

問題はこちら
No.391 CODING WAR - yukicoder

包除原理で殴るだけ
i(≦M)問以下にしか割り当てられないようなパターンは
i問の選び方が $_MC_i$ 、割り当て方がi^Nある。
よって求めるべきは
$\sum_{i=1}^{M}(-1)^{M-i}{}_MC_i\ i^N$ 　（もちろんシグマはi=0からでも構わない）

コンビネーションは、前から何度もやったように（c.f.yukicoder No.250 atetubouのzetubou - メモ）順番に計算できる。
逆元を求める操作は、modを取る数が素数であることからフェルマーの小定理を使えば良い

#define P 1000000007
long pom(long a,long i,long m){return i?pom(a*a%m,i/2,m)*(i%2?a:1)%m:1;}
//このたびmodpowをライブラリ化しました

int main(){
	long n,s=0,t=1;
	int m,i;
	scanf("%ld%d",&n,&m);
	for(i=1;i<=m;i++)s+=p(-1,m-i)*(t=t*(m-i+1)%P*pom(i,P-2,P)%P)*pom(i,n,P)%P+P;
	//負の数を足してしまうと最後に剰余を取るのがめんどくさくなるので、予めPを足して正にしておく
	s=!printf("%d",s%P);
}

modpowの引数にlongって書くのやだ。サボる
tも初期値1を与えるならmainの引数にしておきたい。intでも大丈夫かな…

long n,s;
P=1e9+7,m,i;
long p(a,i){return i?p(1L*a*a%P,i/2)*(i%2?a:1)%P:1;}
main(t){
	for(scanf("%ld%d",&n,&m);m/++i;s+=p(-1,m-i)*(t=t*p(i,P-2)%P*(m-i+1)%P)*p(i,n%~-P)%P+P);
	//tの計算部分でpomの返り値がlongであることを利用するために掛ける順序を入れ替えた
	//また、pの第二引数をintに収めるために、nをp-1で割った余りを渡している（フェルマーの小定理）
	s=!printf("%d",s%P);
}

189B
ideoneでは(longをlong longにするだけじゃなく)pの引数の型をintと明示しないと何故かバグる
型を省略した時の挙動はよくわからない…