AtCoder ABC198 F

题目链接

AtCoder Beginner Contest 198 F-Cube

题意

一个立方体的六个面上各写了一个正整数，问有多少种方案使得六个数之和为 (S) 。

这里假定数字没有方向，即把立方体各种翻转的情况视为同一种方案。

(6leq Sleq 10^{18})

思路

有三种做法：

利用 (Pacute{o}lya) 定理计算
组合数大力分类讨论
手推/ (OEIS) 生成函数

太naïve了，赛时写的第二种，结果没有调完，这里主要讲第一种做法。

立方体翻转总共有 (24) 种情况，记 (G) 为这些置换方式的群，根据 (Pacute{o}lya) 定理，答案为

[frac{1}{|G|}sum_{gin G}c_0(g) ]

那么我们便需要对于每个 (g)，计算 (c_0(g)) 的大小，考虑有哪些情况，(24) 个置换其实可以手算，但是因为懒~~（没凑齐）~~ 就打了个表，代码：

#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define VI vector<int> 
using namespace std;
vector<VI> rotate;
bool tf[7];
map<VI, bool> vis;
VI mul(int x, int y){
    VI a = rotate[x], b = rotate[y];
    rep(i,0,5) a[i] = b[a[i]-1];
    return a;
}
void print_circle(VI p){
    mem(tf, 0);
    rep(i,1,6){
        if(tf[i]) continue;
        cout<<"("<<i;
        int j = p[i-1];
        while(j != i) cout<<" "<<j, tf[j]=true, j = p[j-1];
        cout<<") ";
    }
    cout<<endl;
}
int main(){
    int t = 720;
    rotate.push_back({2, 6, 3, 4, 1, 5});
    rotate.push_back({2, 3, 1, 6, 4, 5});
    vis[rotate[0]] = true;
    vis[rotate[1]] = true;
    int j = 0;
    while(++j <= rotate.size()){
        print_circle(rotate[j-1]);
        VI nxt;
        rep(i,0,j-2) if(!vis[nxt = mul(j-1, i)]){
            vis[nxt] = true;
            rotate.push_back(nxt);
        }
    }
    return 0;
}

打表结果：

(1 2 6 5) (3) (4)
(1 2 3) (4 6 5)
(1 6) (2 3) (4 5)
(1 5 4) (2 3 6)
(1 5 6 2) (3) (4)
(1) (2 3 5 4) (6)
(1 4 2) (3 5 6)
(1 4 6 3) (2) (5)
(1) (2) (3) (4) (5) (6)
(1 4 5) (2 6 3)
(1 4) (2 5) (3 6)
(1 2) (3 4) (5 6)
(1 6) (2) (3 4) (5)
(1 5) (2 6) (3 4)
(1) (2 5) (3 4) (6)
(1 6) (2 5) (3) (4)
(1 6) (2 4) (3 5)
(1 5 3) (2 4 6)
(1) (2 4 5 3) (6)
(1 2 4) (3 6 5)
(1 3 6 4) (2) (5)
(1 3 5) (2 6 4)
(1 3) (2 5) (4 6)
(1 3 2) (4 5 6)

可以注意到总共有 (5) 种形式：

(1+1+4) *6
(3+3) *8
(2+2+2) *6
(1+1+1+1+1+1) *1
(1+1+2+2) *3

计算时预先将 (S) 减去 (6)，把限制放宽到非负整数，前 (4) 种情况很好算，简单提一下第 (5) 种情况。

设 (S) 中去掉两个单独的数之后还剩 (2k)，("1+1") 的方案是 (S-2k+1) 种，("2+2") 的方案是 (k+1) 种，记 (c=frac{S}{2})，从而答案为

[sum_{k=0}^c(k+1)(S-2k+1)\=sum_{k=0}^c((S+1)(k+1)-2k^2-2k)\=frac{(c+1)(c+2)}2(S+1)-frac{2c(c+1)(2c+1)}6-c(c+1)\=frac{(c+1)(c+2)}2(S+1)-frac{c(c+1)(2c+4)}6\=frac{(c+1)(c+2)(3(S+1)-4c)}6 ]

最后把值求和再除以 (24) 即得所求答案。

实现细节

由于有些地方需要判断 (S) 的整除情况以及利用向下取整的除法，读入时不能直接对 (S) 取模。
一些计算过程涉及到了减法，最后输出 (ans) 的时候不要忘记把它拉成正数。

Code

#include<iostream>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define mod 998244353
#define ll long long
using namespace std;
ll inv(ll x){
    ll ret = 1, pow = mod-2;
    for(; pow; pow >>= 1){
        if(pow&1) (ret *= x) %= mod;
        (x *= x) %= mod;
    }
    return ret;
}
ll C(int n, int m){
    ll ret = 1;
    per(i,n,n-m+1) (ret *= i) %= mod;
    rep(i,1,m) (ret *= inv(i)) %= mod;
    return ret;
}
int main(){
    ll S;
    cin >> S;
    S -= 6;

    ll tmp, ans = 0;
    // (1+1+4) *6
    ll s = (S/4) % mod;
    tmp = (s+1) * (S%mod+1-2*s) % mod;
    (ans += 6*tmp) %= mod;

    // (3+3) *8
    if(S%3 == 0){
        tmp = (S/3+1) % mod;
        (ans += 8*tmp) %= mod;
    }

    // (1+1+2+2) *3
    ll c = (S/2) % mod;
    tmp = (3*(S+1)%mod-4*c)%mod * (c+2)%mod * (c+1)%mod * inv(6)%mod;
    (ans += 3*tmp) %= mod;

    // (2+2+2) *6
    if(S%2 == 0){
        tmp = C((S/2+2)%mod, 2);
        (ans += 6*tmp) %= mod;
    }

    // (1+1+1+1+1+1) *1
    tmp = C((S+5)%mod, 5);
    (ans += tmp) %= mod;

    (ans *= inv(24)) %= mod;
    cout << (ans+mod)%mod << endl;
    return 0;
}