min min min min sum

2 secs 1024 MB

$問題を次のように言い換えることができます。$
$(問題) = 1 × (min(i,j,k,l)が1になる回数) + 2 × (min(i,j,k,l)が2になる回数) +... + N × (min(i,j,k,l)がNになる回数) このようになります。$

$次に各値の出現回数について求めていきます。$ 変数が4つあっては考えづらいので、 $\displaystyle\sum^{N}_{i=1}$ $\displaystyle\sum^{N}_{j=1}$ $min(i,j)$ で考えます。
$min(i,j) = N となる(i,j)の組み合わせは (i,j) = (N,N)しかありません.$ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 $min(i,j) = N-1となる(i,j)の組み合わせは (i,j) = (N-1,N-1) , (N-1,N) , (N,N-1)の三通りになります。$

$min(i,j) = N-1となる組み合わせは、(N-1,Nの二つを使って表すことのできる組み合わせの数) - (N,Nを使って表すことのできる組み合わせの数)とできます。$ $一般に値Xの出現回数を数式で表すと、(min(i,j) = Xとなる組み合わせの数) =$ $(N-X+1)^{2}$ $-$ $(N-X)^{2}$ $となります。元の問題はこの指数部分が4のものを解けば良いので、下記のようなコードで解くことができます。計算量は$ $O(N) になります。$
$実装にはACLのmodintを用いています。$

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std ;
using namespace atcoder ;
using mint = modint998244353 ;

int main(){
    int N ;
    cin >> N ;
  
    mint Answer = 0 ;
    
    for(int i = 1 ;i <= N ;i++){
       Answer += mint(i) * (mint(N-i+1).pow(4) - mint(N-i).pow(4)) ;
    }
  
    cout << Answer.val() << endl;
  
    return 0 ;
}