layout: post
title: "2021-11-27-組合數學測試題解"
date: 2021-11-27
categories: 數學
tags: [數學, 容斥原理]
image:
組合數學測試題解
link
感性觀察+手玩可以在5min內得到結論。
走的路徑如下圖所示。
如果行比列多，就把行列反過來。
得到式子是:\(\dbinom + m\)，上下項的差很小，可以暴力求。
#include #include #include #include #define int long long
using namespace std;
const int maxn = 2000005;
const int mod = 1e9 + 7;
int n, m, ans;
int qpow(int x, int y)
return res;
}int c(int x, int y)
for (int i = 1; i <= x - y; i++)
return res;
}signed main()
其實就是個康託展開。
考試時真心沒搞清楚題意，於是放棄了。。。
但是有重複元素。 可以用如下流程操作。
#include #include #include #include #define int long long
using namespace std;
const int maxn = 55;
char s[maxn];
int n, ans, tot[maxn], c[maxn][maxn];
signed main()
}scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++)
for (int i = 1; i <= n; i++)
tot[j]++;
ans += res;
}tot[s[i] - 48]--;
}printf("%lld\n", ans);
return 0;
}
我是真的腦子進水了。
居然忘了乘每項前的係數，看了半天還沒發現。
直接隔板法。
方案中如果不考慮數字的limit，那麼可以有\(\dbinom\)。
然後列舉有多少個填進去的數不合法。
方案數是 \(\dbinom\)，注意不合法的板子可以插的地方不唯一，要乘上係數 \(\dbinom\)。
結果寫著寫著就忘了。
本題就可以直接奇減偶加容斥求解。
\(ans = \dbinom - ^n} \dbinom \dbinom \times (-1)^i\)
#include #include #include #define int long long
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 998244353;
int t, n, m, k;
ll fac[maxn << 1], inv[maxn << 1], ans;
ll qpow(ll x, int y)
return res;
}ll c(int x, int y)
signed main()
printf("%lld\n", ans);
}return 0;
}
陣列開小了 +cmp函式自帶大場數 + 忘記處理迴圈後的遺留資料 = 0
沒什麼好說的。。。
在**裡把錯誤標出來吧。。。
#include #include #include #include #define ll long long
using namespace std;
const int maxn = 2e6 + 5;
int n, tot[maxn], cnt, ans, sum;
struct node s[maxn], tmp[maxn];
bool check(int x, int y)
return flag;
}bool cmp(node x, node y)
// }
// return true;
return x.key < y.key;
}void read(int& x)
while (c >= '0' && c <= '9')
x *= f;
}signed main()
sort(s[i].v + 1, s[i].v + 1 + 5);
for (int sta = 1; sta < (1 << 5); sta++)
tmp[cnt].wid = p;
} }// double st = time(0);
// printf("%ld\n", st - st1);
sort(tmp + 1, tmp + 1 + cnt, cmp);
// double ed = time(0);
// printf("%lf\n", ed - st); 沒有hash的排序跑了 9ms 哈哈哈哈。。。
// for (int i = 1; i <= cnt; i++)
// printf("\n");
// }
ans = 0, sum = 0;
for (int i = 1; i <= cnt; i++) else
} tot[tmp[cnt - 1].wid] += (sum * (sum - 1)) / 2; // 考試時沒寫，結果過樣例了。哈哈哈哈。
for (int i = 1, sta = 1; i <= 5; i++, sta *= -1)
// printf("%d\n", ans);
printf("%lld\n", ((long long)n * (n - 1) / 2) - ans);
return 0;
}
學組合數學心得與題解（一） 組合計數
今天我在某 上稍微學習了一下組合數學，準確來講，今天就看了看組合計數。像一些弱智的排列數 組合數大家肯定在小學奧數就已經精通了 只有我這種蒟蒻忘的精光 當然，博主比較菜，連二項式定理 帕斯卡恆等式都不會，所以今天只能惡補一下啦。排列數與組合數大家一定都十分的明白了，所以我在這裡也不多說了。然後二項式...
題解 組合數學 排隊
題目描述 n個男生，m個女生，2名老師，任意兩名女生不能相鄰，兩名老師不能相鄰，求解排列方法數。題解 典型的插板法，n個男生先放進去a n,n 然後插入老師，n 1個空位插入2名老師，a 2 最後插入m名女生，a n 3,m 然而並不對。考慮考慮我們漏掉了什麼重要的東西？顯然上面的情形老師之間必然有...
組合語言測試題2
組合語言的主體是 a a.彙編指令 b.機器指令 c.偽指令 d.彙編程式 在組合語言中，能夠翻譯成二進位制 的指令是 a a.彙編指令 b.偽指令 c.機器指令 d.巨集指令 1個cpu能訪問的最大記憶體地址是1023，則該cpu地址匯流排的寬度 b a.8 b.10 c.13 d.14 從200...
組合數解題技巧
首先了解一下組合數 表示的是從m中隨機取出n個。下面是一道經典例題 對於一個n個定點的凸多邊形，他的任何三條對角線都不會交於一點。請求楚圖形中對角線交點的個數。例如，6邊形 輸入輸出格式 輸入格式 第一行一個n，代表邊數。輸出格式 第一行輸出交點數量 輸入輸出樣例 輸入樣例 1 3輸出樣例 1 0輸...
組合數問題 題解
問題和p2822 組合數問題 洛谷基本一樣，除了這道題對組合數重定義了。這道題中組合數 s n,m 表示將 n 個不同的元素拆分成 m 個非空集合的方案數。s 0,0 1,forall i ge 1,s i,0 0 1 le n,le 2000,2 le k le 21,1 le t le 1000...
題解 組合數學 Perm 排列計數
題幹 description 稱一個1,2,n的排列p1,p2 pn是magic的，當且僅當2 i n時，pi pi 2.計算1，2，n的排列中有多少是magic的，答案可能很大，只能輸出模p以後的值 input 輸入檔案的第一行包含兩個整數 n和p，含義如上所述。output 輸出檔案中僅包含一個...
題解 組合數學 DP 地精部落
拿到這道題秒懂題意 波動序列。然鵝不會打。想了一節課，想打純組合數學，結果找不到規律。想的是先假設拍出一個序列，然後交換其中的元素求組合，無奈沒啥規律可循，顯然不能一口氣求出來 我說的是我沒辦法，網上大佬們有的是辦法 然後想dp，挨個插入，妄圖一維dp走起，結果摔倒在地 然後我就不是人了。廢話 稱n...
組合數學八題
1.1 n,m 1000 2.所有答案對1000007 10 6 7 取模 3.每道題只有一個點，一個點有多組資料 4.輸入格式 第一行整數t t 10 表示資料組數 接下來t行每行兩個數表示n,m 5.時間限制為1s，空間限制為256mb 6.檔名為x.pas c cpp，輸入為x.in，輸出為x...
組合數學兩題
codechef c3prb3 題意 給你一個陣列，然後問其中的奇數個數的子集的中位數和是都少。思路 先對陣列內的元素進行一次排序，然後對於每個數字，選擇在它之前和在它之後的較小值m。然後c m,i i from 0 to m 然後乘上對應的數。累加即得答案。include include incl...
題解 NOIP2016 組合數問題
第一行有兩個整數t,k，其中t代表該測試點總共有多少組測試資料，k的意義見 問題描述 接下來t行每行兩個整數n,m，其中n,m的意義見 問題描述 t行，每行一個整數代表所有的0 i n,0 j min i,m 中有多少對 i,j 滿足c j,i 是k的倍數。輸入1 1 2 3 3 輸入2 2 5 4...