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 |
|
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 |