CF 1228 C数論D図論/hash E dp
C Primes and Multiplication
x(1 e 9)とn(1 e 18)が与えられ、xの全ての質量因子yに対して、1~nの各数に対して最大でyのべき乗数の因子zが計算する、これらのzに対して積が求められる.xの質因子はよく求められる.第2のステップは、1からnまでのすべての数を列挙して2点にすることはできません.aはxの質量因子の一つであると仮定した.1~nがaで割り切れる数はn/a個、1~nがa 2 a^2 a 2で割り切れる数はn/(a 2)n/(a^2)n/(a 2)個、1~nがa 3 a^3 a 3で割り切れる数はn/(a^3)n/(a 3)個…そしてこれらの数に対して1つのcnt配列を得ることができ、cnt[i]はaのi次方がcnt[i]個数の因子であることを示すことが考えられる.しかし,問題が求めるのは各数の最大因子であるため,(cnt[i]-cnt[i+1])はaのi次方を最大因子とする数の個数であり,aの答えへの寄与は(cn t[i]-cn t[i+1])∗i+(cn t[i+1]-cn t[i+2])∗(i+2)+.+である.( c n t [ n ] − c n t [ n + 1 ] ) ∗ n (cnt[i]-cnt[i+1])*i+(cnt[i+1]-cnt[i+2])*(i+2)+...+(cnt[n]-cnt[n+1])*n (cnt[i]−cnt[i+1])∗i+(cnt[i+1]−cnt[i+2])∗(i+2)+...+(cnt[n]−cnt[n+1])∗n.この少し簡略化はΣcn tsum{cnt}Σcntである.これにより、a毎にこのような方法で1回通過するだけでよい.
D Complete Tripartite
n個の点、m個の辺を与える、n個の点を3部に分けることができるかどうかを問う、各部分の内部に辺がなく、各点はグループ外(他の2つのグループの)すべての点に辺があり、パケット方式を出力する.グループ番号のみが異なる場合を考慮しないで、実際には1つのグループ化方式しかないことは明らかである.最初のエッジについて、前の2つのグループの最初の2つのポイントを決定することができ、残りのポイントの配置方法は既定で唯一である:第1のグループのheadとエッジがあるかどうかを見て、ないかを見て、次のグループを順番にチェックする...これによって、各グループのheadと他のメンバーがエッジがないようにグループ化することができる.エッジがない以上、もちろんグループに入れます.だからこの方法は正しいか、合法的な方法がない.次の仕事は、この正しいグループ化方式が合法かどうかを検査することです.もし彼が合法なら、これが正しい答えです.合法でなければ、正しい答えはない.実際には、同じグループ内の点がグループ外の各点に1つのエッジを有することを発見することができ、それは、同じグループ内の各点に対して、そのすべてのエッジを格納する別の端点が配列sにおいて、各点のs配列が同じであることを意味する.これにより、各点のs配列の前処理(hash)を1つの値にすることができる.では、前のグループ方式をチェックするには、各グループ内のhash値が統一するか否かを判断するだけでよい.
E Another Filling the Grid
n*n(n<=250)の格子を与え、格子に数(1からk)を記入するが、各行の列ごとに1があることを保証し、どれだけの中記入案があるかを聞く.明らかにdp dp[i][j]は、前i行にj個の保証された列があることを示すシナリオ数である.壹dp[i][j]は、まず前の行、同じjからの移行が可能である.このとき、この行(i行目)は少なくとも1つ(この行が1であることを保証する)を置く、前の行が1である列に置く(jを拡大できない).すなわち、1を見逃す列にはk-1種の置き方があり、1を見逃す列の置き方数は、全てを適当に(1列当たりk種の置き方)-1個もない(1列当たりk-1種の置き方)に相当する.斜体部分は、1つを選択して1を置き、その他は任意の数を置く(Cj 1∗(j−1)kC^{1}{j}*(j-1)^k Cj 1∗(j-1)k)は、計算を繰り返すためである.
贰はj-1から移転して、つまり1を逃していない列を追加して、今この行で1を放します.すなわち、1を見逃す列は任意に置き、1を見逃さない列は1を選び、その他はk-1の数を置く.でもj-2から移すこともできますよ.したがって、この行がどれだけ1つ置かれているかを列挙する.すなわち、i,jはi−1,k(k from 0 to j−1)から移行すべきである.
x(1 e 9)とn(1 e 18)が与えられ、xの全ての質量因子yに対して、1~nの各数に対して最大でyのべき乗数の因子zが計算する、これらのzに対して積が求められる.xの質因子はよく求められる.第2のステップは、1からnまでのすべての数を列挙して2点にすることはできません.aはxの質量因子の一つであると仮定した.1~nがaで割り切れる数はn/a個、1~nがa 2 a^2 a 2で割り切れる数はn/(a 2)n/(a^2)n/(a 2)個、1~nがa 3 a^3 a 3で割り切れる数はn/(a^3)n/(a 3)個…そしてこれらの数に対して1つのcnt配列を得ることができ、cnt[i]はaのi次方がcnt[i]個数の因子であることを示すことが考えられる.しかし,問題が求めるのは各数の最大因子であるため,(cnt[i]-cnt[i+1])はaのi次方を最大因子とする数の個数であり,aの答えへの寄与は(cn t[i]-cn t[i+1])∗i+(cn t[i+1]-cn t[i+2])∗(i+2)+.+である.( c n t [ n ] − c n t [ n + 1 ] ) ∗ n (cnt[i]-cnt[i+1])*i+(cnt[i+1]-cnt[i+2])*(i+2)+...+(cnt[n]-cnt[n+1])*n (cnt[i]−cnt[i+1])∗i+(cnt[i+1]−cnt[i+2])∗(i+2)+...+(cnt[n]−cnt[n+1])∗n.この少し簡略化はΣcn tsum{cnt}Σcntである.これにより、a毎にこのような方法で1回通過するだけでよい.
D Complete Tripartite
n個の点、m個の辺を与える、n個の点を3部に分けることができるかどうかを問う、各部分の内部に辺がなく、各点はグループ外(他の2つのグループの)すべての点に辺があり、パケット方式を出力する.グループ番号のみが異なる場合を考慮しないで、実際には1つのグループ化方式しかないことは明らかである.最初のエッジについて、前の2つのグループの最初の2つのポイントを決定することができ、残りのポイントの配置方法は既定で唯一である:第1のグループのheadとエッジがあるかどうかを見て、ないかを見て、次のグループを順番にチェックする...これによって、各グループのheadと他のメンバーがエッジがないようにグループ化することができる.エッジがない以上、もちろんグループに入れます.だからこの方法は正しいか、合法的な方法がない.次の仕事は、この正しいグループ化方式が合法かどうかを検査することです.もし彼が合法なら、これが正しい答えです.合法でなければ、正しい答えはない.実際には、同じグループ内の点がグループ外の各点に1つのエッジを有することを発見することができ、それは、同じグループ内の各点に対して、そのすべてのエッジを格納する別の端点が配列sにおいて、各点のs配列が同じであることを意味する.これにより、各点のs配列の前処理(hash)を1つの値にすることができる.では、前のグループ方式をチェックするには、各グループ内のhash値が統一するか否かを判断するだけでよい.
E Another Filling the Grid
n*n(n<=250)の格子を与え、格子に数(1からk)を記入するが、各行の列ごとに1があることを保証し、どれだけの中記入案があるかを聞く.明らかにdp dp[i][j]は、前i行にj個の保証された列があることを示すシナリオ数である.壹dp[i][j]は、まず前の行、同じjからの移行が可能である.このとき、この行(i行目)は少なくとも1つ(この行が1であることを保証する)を置く、前の行が1である列に置く(jを拡大できない).すなわち、1を見逃す列にはk-1種の置き方があり、1を見逃す列の置き方数は、全てを適当に(1列当たりk種の置き方)-1個もない(1列当たりk-1種の置き方)に相当する.斜体部分は、1つを選択して1を置き、その他は任意の数を置く(Cj 1∗(j−1)kC^{1}{j}*(j-1)^k Cj 1∗(j-1)k)は、計算を繰り返すためである.
dp[i][j]=dp[i-1][j]*((K[j]+mod-K_1[j])%mod)%mod*K_1[n-j]%mod;
贰はj-1から移転して、つまり1を逃していない列を追加して、今この行で1を放します.すなわち、1を見逃す列は任意に置き、1を見逃さない列は1を選び、その他はk-1の数を置く.でもj-2から移すこともできますよ.したがって、この行がどれだけ1つ置かれているかを列挙する.すなわち、i,jはi−1,k(k from 0 to j−1)から移行すべきである.
for(int p=j-1; p>=0; p--) {
dp[i][j]=(dp[i][j]+
dp[i-1][p]*C[n-p][j-p]%mod*K[p]%mod*K_1[n-j]%mod)%mod;
}