Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2289-f4750d05
この記事にトラックバックする(FC2ブログユーザー)

ARC 004 D - 表現の自由 (Freedom of expression) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #004
問題文

問題概要

問題文が簡単なのでそのまま転載する.
整数 N (絶対値は10^9以下) と M (10^5以下) が与えられる時、整数 N を M 個の整数の積で表す方法は何通りあるでしょうか。
その答えを 1,000,000,007 で割った余りを答えてください。
補足:1*2と2*1は別とみなす.

解法

各素因数ごとに,M個のどこに割り振るか,重複組合せの数をかけていく.
-1は何個使うかを場合分けして,重複組合せの数を足していく.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007

void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
  r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
  while(r1>0){
    q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
    r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
  }
  *c=r0; *a=a0; *b=b0;
}

ll get_inv(ll n, ll p){
  ll a,b,c;
  extended_euclid(n,p,&c,&a,&b);
  if(a<p) a+=p;
  return a%p;
}

int getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}
int ps, p[100000];
ll fact[200000], fact_inv[200000];

ll mulcom(ll a, ll b){
  ll res;
  if(b < 0) return 0;
  res = (fact[a+b-1] * fact_inv[a-1])%M * fact_inv[b];
  res %= M;
  return res;
}

ll com(ll a, ll b){
  ll res;
  if(b < 0 || b > a) return 0;
  res = (fact[a] * fact_inv[a-b])%M * fact_inv[b];
  res %= M;
  return res;
}

int main(){
  int i,j,k,l;
  int n, m, fg;
  int arr[100], arr_size;
  ll res, mul;

  fact[0] = 1;
  REP(i,1,200000) fact[i] = (fact[i-1]*i)%M;
  rep(i,200000) fact_inv[i] = get_inv(fact[i], M);

  fg = 0;
  scanf("%d%d",&n,&m);
  if(n<0) n=-n, fg = 1;

  ps = getPrime(100000,p);
  res = 1;

  rep(i,ps){
    if((ll)p[i] * p[i] > n) break;
    k = 0;
    while(n%p[i]==0) n/=p[i], k++;
    if(k==0) continue;
    res *= mulcom(m, k);
    res %= M;
  }
  if(n > 1){
    res *= m;
    res %= M;
  }

  mul = 0;
  for(i=fg;i<=m;i+=2){
    mul += com(m,i);
  }
  mul %= M;

  res = (res*mul)%M;

  printf("%d\n",(int)res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2289-f4750d05
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。