UVa11718 - Fantasy of a Summation(Math theorm)

題目大意

給你一份 code 請你釐清他，並將它用更好的方式寫出來。
題目連結

重點觀念

• 數學XD

分析

• 可以看得出來程式碼是一種排列。
• 將它實際畫出來後，可以發現組合為

  1 1 1 
  1 1 2
  1 2 1
  1 2 2 
  2 1 1
  2 1 2
  2 2 1
  2 2 2

• 可以發現，在同個 column 中，每一個數字的使用次數都相同。
  • 可以將數字做總和，並乘以使用次數，在乘以 column 就能找到答案
• 怎麼知道數字的使用次數?
  • 如果我們看第一排的 1，可以發現後面每一列都使用了 2 個數字，且有兩列，因此就可以得出第一排的 1 用了幾次
  • 得出公式 \(n^{(k-1)} \)，其中 \( k-1\) 是減去第一行
• 在來使用快速次方，來計算答案。
• 記住，在每次計算中都必須先除以題目給的 mod。否則會 overflow。
• 因此公式就是
  • \(sum = 所有數字總和 \)
  • \(sum * (n^{(k-1)} * k))
  • 數字總和 * 每一列數字使用次數 * 有幾欄
  • 記住，每次相乘完要 mod 避免 overflow。

心得

好久沒有寫快速次方，都忘記了XD，還有 mod，記住一定要在各種乘號，以及累加先做 mod，避免 overflow….。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int unsigned long long
using namespace std;
const int MAXN = 1020;
int num[MAXN];
int t, n, k, mod, kase = 0;

int pow(int x,int y){
    if(y == 0) return 1;
    int ans = pow(x, y/2) % mod;
    if(y % 2 == 1) ans = (ans * ans % mod) * x % mod; //有乘號就 mod 避免 overflow
    else ans = ans * ans % mod;
    return ans;
}
// 快速次方核心
// 從次方(二進位)右邊開始看，如果碰到 1 就多 * 2

//EX: 2^5 5 = 101(2)
//1*1*2 = 2; 
//2*2 = 4;
//4*4*2 = 32;
//其中為甚麼碰到 1 就要多乘 2？
//當你只有 4*4 = 16，也就是 2^4， 4=100(2)
//也就是說，當你多 * 2 表示多了一個次方。因此 4 的二進位也加一，就成為 5=101(2)


int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k >> mod;
        for(int i = 0; i < n; i++) cin >> num[i];
        int sum = num[0] ;
        for(int i = 1; i < n; i++) sum = (sum + num[i]) % mod;
        int ans =  (sum * (pow(n, k-1) %mod) * (k % mod) ) % mod;
        cout << "Case " << ++kase << ": " << ans << "\n";
    }

    return 0;
}