Submission #24041


Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
vector<vector<int> > res;
map<int,int> d;
vector<int> cnt;
typedef long long lli;
const lli MOD=1000000007;
long long gcd(long long a,long long b){
	return b>0?gcd(b,a%b):a;
}
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
long long extgcd(long long a,long long b,long long &x,long long &y){
	long long d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);y-=(a/b)*x;
	}else{
		x=1;y=0;
	}
	return d;
}
long long mod_inverse(long long a,long long M){
	long long x,y;
	extgcd(a,M,x,y);
	return (M+x%M)%M;
}
void bunkai(int target,int min){
	if(target==1){
		res.push_back(cnt);
		return;
	}
	for(int i=min;i*i<=target;i++){
		if(target%i==0){
			cnt.push_back(i);
			bunkai(target/i,i);
			cnt.pop_back();
		}
	}
	if(target<min)return;
	cnt.push_back(target);
	bunkai(1,target);
	cnt.pop_back();
}
const int MAX_M=100005;
lli pow[MAX_M+1];
lli pow_inv[MAX_M+1];
#define REP(i,x)for(int i=0;i<(int)x;i++)
lli comb(int n,int k){
	return ((lli)(pow[n]*pow_inv[k])%MOD*pow_inv[n-k])%MOD;
}
int main(void) {
	lli N,M;
	cin>>N>>M;
	int sign=1;
	if(N<0){
		N*=-1;
		sign*=-1;
	}
	bunkai(N,2);
	lli ans=0;
	pow[0]=1;
	REP(i,MAX_M){
		pow[i+1]=(lli)(pow[i]*(i+1))%MOD;
	}
	REP(i,MAX_M){
		pow_inv[i]=mod_inverse(pow[i],MOD);
	}
	REP(i,res.size()){
		if(i>0&&res[i]==res[i-1]){
			cerr<<"不正な計算結果なのです!"<<endl;
		}
		int cnt=1;
		lli tres=pow[res[i].size()];
#if 0
		REP(j,res[i].size()){
			cout<<res[i][j]<<" ";
		}

		cout<<endl;
#endif
		if(res[i].size()>M)continue;
		lli tdiv=1;
		for(int j=1;j<(int)res[i].size();j++){
			if(res[i][j]==res[i][j-1]){
				cnt++;
			}else{
				tdiv*=pow_inv[cnt];
				tdiv%=MOD;
				cnt=1;
			}
		}
		tdiv*=pow_inv[cnt];
		tdiv%=MOD;
		//ans+=(comb(M,res[i].size())*((tres*tdiv)%MOD))%MOD;
		tdiv*=pow_inv[M-res[i].size()];
		tdiv%=MOD;
		ans+=(pow[M]*tdiv)%MOD;
		ans%=MOD;
		//cout<<(pow[M]*tdiv)%MOD<<endl;
		//cout<<tres*tdiv<<endl;
		//cout<<comb(M,res[i].size())<<endl;


	}
	lli sign_data=0;
	REP(i,M+1){
		if((sign==1)^(i%2==1)){
			sign_data=(sign_data+comb(M,i))%MOD;
		}
	}
	cout<<(ans*sign_data)%MOD<<endl;
	return 0;
}

Submission Info

Submission Time
Task D - 表現の自由 ( Freedom of expression )
User nomeaning
Language C++ (G++ 4.6.4)
Score 100
Code Size 2314 Byte
Status AC
Exec Time 469 ms
Memory 63008 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 40
Set Name Test Cases
All 00_max.txt, 00_max2.txt, 00_max3.txt, 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 04_primes_01.txt, 04_primes_02.txt
Case Name Status Exec Time Memory
00_max.txt AC 469 ms 63008 KB
00_max2.txt AC 96 ms 4268 KB
00_max3.txt AC 83 ms 2940 KB
00_min.txt AC 75 ms 2292 KB
00_sample_01.txt AC 76 ms 2264 KB
00_sample_02.txt AC 96 ms 4276 KB
00_sample_03.txt AC 76 ms 2288 KB
00_sample_04.txt AC 77 ms 2296 KB
01_rnd_00.txt AC 79 ms 2300 KB
01_rnd_01.txt AC 76 ms 2296 KB
01_rnd_02.txt AC 77 ms 2304 KB
01_rnd_03.txt AC 77 ms 2296 KB
01_rnd_04.txt AC 78 ms 2308 KB
01_rnd_05.txt AC 77 ms 2296 KB
01_rnd_06.txt AC 77 ms 2300 KB
01_rnd_07.txt AC 77 ms 2272 KB
01_rnd_08.txt AC 77 ms 2296 KB
01_rnd_09.txt AC 78 ms 2292 KB
01_rnd_10.txt AC 77 ms 2296 KB
01_rnd_11.txt AC 78 ms 2288 KB
01_rnd_12.txt AC 79 ms 2292 KB
01_rnd_13.txt AC 87 ms 2360 KB
01_rnd_14.txt AC 78 ms 2292 KB
01_rnd_15.txt AC 76 ms 2288 KB
01_rnd_16.txt AC 78 ms 2288 KB
01_rnd_17.txt AC 78 ms 2300 KB
01_rnd_18.txt AC 78 ms 2276 KB
01_rnd_19.txt AC 78 ms 2304 KB
01_rnd_20.txt AC 76 ms 2300 KB
01_rnd_21.txt AC 78 ms 2272 KB
01_rnd_22.txt AC 78 ms 2300 KB
01_rnd_23.txt AC 78 ms 2300 KB
01_rnd_24.txt AC 77 ms 2288 KB
01_rnd_25.txt AC 78 ms 2296 KB
01_rnd_26.txt AC 78 ms 2296 KB
01_rnd_27.txt AC 76 ms 2296 KB
01_rnd_28.txt AC 80 ms 2304 KB
01_rnd_29.txt AC 79 ms 2296 KB
04_primes_01.txt AC 78 ms 2308 KB
04_primes_02.txt AC 79 ms 2296 KB