T1:
一道十分奇妙的人类智慧题......二次函数(求导)易证题面中给的那个操作就是求算术平均值......然后我发现每次操作相当于把坐标对答案的贡献乘以1/k,然后就失去梦想写暴力了......考虑这个暴力怎么写,任凭实数炸精度显然是不行的,我们可以在mod 998244353下计算坐标,把最终答案都丢进一个set里面,最后输出它的size。我们在dfs的时候可以用vector传递一个状态,在dfs中next_permutation枚举下一个状态(钦定前k个进行合并)。由于这么枚举状态会dfs到重复状态,所以我们要对表示状态vector再次哈希判重。(话说这又是vector又是set又是哈希套哈希的居然还能有15分)考虑正解,显然我们可以把合并操作建立成一棵满k叉树。对于同一层的所有点,我们可以排序;对于一个非叶子节点,如果它的孩子的颜色全部相同,那么我们可以删去它的孩子把自己变成一个和孩子颜色相同的点。通过这样的操作,我们一定能把一棵满k叉树变成每一层只有k-1个叶子和一个中间节点(最深层k个叶子)的形态,并且由于深度+1使得贡献乘以1/k,这种树一定一一对应一个最终位置(虽然不一定合法)。如果我们设树的深度为x,黑点总数为y,那么这样的树的个数就是一个经典的数位DP问题(长度为x的k进制数,数字和为y)。但是这样存在后缀零,计算答案时去掉后缀零的话,我们让dp[x][y]减去dp[x-1][y]就好了。考虑这样的树什么情况下合法,我们需要把它还原回去,计算黑色节点总数和白色节点总数。显然一次缩点操作减少k-1个节点,所以如果n-黑色点总数或者m-白色点总数取模k-1不为0的话,肯定不行。然后就能AC啦。15分暴力代码:1 #include2 #define debug cout 3 using namespace std; 4 typedef long long int lli; 5 const int mod=998244353; 6 7 inline lli fastpow(lli base,int tim) { 8 lli ret = 1; 9 while(tim) {10 if( tim & 1 ) ret = ret * base % mod;11 if( tim >>= 1 ) base = base * base % mod;12 }13 return ret;14 }15 16 set vis;17 set st;18 19 int n,m,k,inv;20 21 inline bool judge(const vector &v) {22 unsigned long long int hsh = 0;23 for(unsigned i=0;i