CF 1228 C 数论 D 图论/hash E dp

C Primes and Multiplication

给出x(1e9)和n(1e18), 对于x的所有质因子y, 对于1到n每个数计算最大的是y的幂次的因子z, 对于这些z求乘积.

x的质因子很好求. 第二步我们总不能枚举1到n所有的数然后二分来做.

我们假设a是x的质因子之一.

可以想到, 1到n能被a整除的数恰好是n/a个, 1到n能被 a 2 a^2 a2整除的数恰好是 n / ( a 2 ) n/(a^2) n/(a2)个, 1到n能被 a 3 a^3 a3整除的数恰好是 n / ( a 3 ) n/(a^3) n/(a3)个…

然后对于这些个数我们就能得到一个cnt数组, cnt[i]表示a的i次方是cnt[i]个数的因子.

但是我们注意到, 题目所求是每个数的最大因子, 所以(cnt[i]-cnt[i+1])就是以a的i次方为最大因子的数的个数, 那么a对答案的贡献就是 ( c n t [ i ] − c n t [ i + 1 ] ) ∗ i + ( c n t [ i + 1 ] − c n 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. 这个稍微化简一下就是: ∑ c n t \sum{cnt} ∑cnt.

这样只需要将每个a按这样的方式过一遍就可以了.

D Complete Tripartite

给出n个点, m条边, 问能否将n个点分成3份, 每部分内部没有边, 每个点向组外(另外两个组的)所有的点都有边, 输出分组方式.

很显然其实只有一种分组方式(不考虑只有组号不同的情况).

对于第一条边就能确定前两个组的开始的两个点, 剩下的点的放置方式是既定而唯一的: 看和第一组的head有无边, 没有就放, 有则依次检查下面的组…

这样会得到一种分组方式, 使得每组的head和其他成员都没边. 既然没有边, 当然要放到一组. 所以这种方式要么是对的, 要么就没有合法的方式. 下面的工作就是检查这个可能正确的分组方式是否合法. 如果他合法, 那这个就是正确答案; 如果不合法, 那么就没有正确答案.

其实, 我们可以发现, 同组内的点都向组外的每个点有一条边, 那么就意味着, 如果对于同组内的每个点, 储存其所有连边的另个端点到数组s中, 每个点的s数组都是相同的. 这样可以将每个点的s数组预处理(hash)成一个值. 那么检查前面的分组方式只需确定每个组组内的hash值是否统一.

E Another Filling the Grid

给出一个n*n(n<=250)的格子, 向格子里填数(1到k), 但要保证每行每列都有1, 问有多少中填数方案.

显然是dp

dp[i][j]表示前i行有j个已经保证有1的列的方案数.

壹 dp[i][j]首先可以由上一行, 相同j的转移. 此时, 这一行(第i行)至少放1个1(保证这行有1), 且要放在上一行已经有1的列(不能扩大j). 即: 没放过1的列有k-1种放法, 放过1的列的放法数相当于: 全都随便放(每列k种放法)-没有一个1(每列k-1种放法).

斜体部分不能是: 选一个放1, 其他放任意数( C j 1 ∗ ( j − 1 ) k C^{1}_{j}*(j-1)^k Cj1​∗(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)转移

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