A 大模擬，我跟lin理解錯題意。
#includeE 水概率，沒想到這麼水。。。！！#include using namespace std; int events[100005]; int main() { int t; scanf(%d, &t); for (int i = 1; i <= t; i++) { long long n, a, b, s; cin >> n >> a >> b; s = a * 2 + b; for (int j = 0; j < n; j++) { cin >> events[j]; } for (int j = 1; j < n; j++) { double back, stay; back = a * 2 + b; stay = (events[j] - events[j - 1]) * b; if (back > stay) s = s + stay; else s = s + back; } cout << Case # << i << : << s << endl; } return 0; }
#include#include using namespace std; int main(){ int t; cin>>t; int kase = 1; while (t--) { int m, k; cin>>m>>k; double ans = 1.0 / ((m+1)*(k)+1); cout << Case # << kase++ << : << fixed << setprecision(8) << ans << endl; } }
周五去跟小政政上自習了，嘯爺他們自己做的，貌似太難。。
http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=103#overview
出題人總結：http://hi.baidu.com/wzc1989/item/56ce9291cdfdc0bf82d29548
B題過的，這。。
#include#define LL long long using namespace std; int a[1000005]; int main() { int t; scanf(%d, &t); for (int case1 = 1; case1 <= t; case1++) { int n; cin>>n; LL l = 0, r = 0; for (int i = 0; i < n; i++) { scanf(%d, &a[i]); if (i && a[i] > a[i - 1]) { l += (LL)a[i] - a[i - 1]; } if (i && a[i] < a[i - 1]) { r += a[i - 1] - a[i]; } } cout << Case <<case1 <<="" :="" max(l,="" r)="" '="" abs(a[0]="" -="" a[n="" 1])="" +="" 1="" endl;="" }="" return="" 0;="" 結論題="" 這源於tju的一份神奇代碼，於是這題變成了可以秒殺的結論題了。="" 本機暴力了一萬組小數據都沒有問題,那麼這樣寫應該是沒有問題的，不過感覺有點匪夷所思,至少我不明白為什麼(早知道就可以出得更離譜了J尤其是第二個答案竟然只跟首尾有關)
呵呵，呵呵，呵呵。
重點是下面這個題
G
做題的時候一直糾結於所謂“部分錯排公式”。的確有那麼個公式：
n + m 個數中 m 個數必須錯排求排列數
dp[m] 為所求解
可是這不扯呢麼，開都開不開，而且也不能預處理取模運算，存也存不下。。
解題報告：
其中C(n,n - k)表示組合數 H(n - k)表示錯排數 由於n,k的規模比較大，於是無法直接暴力 而由於m不一定為square-free-number,多以CRT(Chinese Remainder Theorem)+LUCAS也是無法行得通的。
首先我們先來解決 C(n,k) mod m的問題
做法是先將m分解成若干的素因子的冪次的乘積，之後對於每一個 Pi^Ki 計算 C(n,k) mod Pi^Ki，之後的結果用CRT合並得到 下面介紹如何計算 C(n,k) mod Pi^Ki 做法很簡單
我們開一個全局變量，保存C(n,k)中的Pi的個數(可以容易得到)補充：采用整數分解的方式，pollard-rho方法。
現在的問題就是如何處理不含Pi的連續若干個數字的乘積
其中Cnt[i]表示(i!)中Pi的個數
其中Inv(x) 表示x對m的逆元，C[i]表示i中Pi的個數.補充：對應除一下， 那麼
Tot 表示C(n,k)中Pi的個數. 顯然F[i]表示的是不含有Pi的積 下面考慮F[i] 那麼可以預處理得到F[1...m - 1] 可是實際上我們需要的其實是F[n],由於n比較大,沒有辦法預處理,不過通過觀察不難發現F[i]具有周期性，於是可以利用周期性來求解.最後將得到的答案利用CRT合並得到C(n,k) mod m的結果。 之後說說H(n - k)的求法，可以證明 本題 中 H(i) mod m存在周期！於是繼續使用周期的思路來處理就可以得到答案。
代碼是參考別人思路寫出的：
#include#include #include #include #include using namespace std; #define F 200 #define M 200010 long long n, K, m; long long mp[F], mr; long long xa[F], xb[F], xc[F]; long long circle[M] = { 1 }; void divide_factor(long long x) { long long i, k; k = (long long)sqrt((double)x) + 1; mr = 0; for (i = 2; i <= k && x != 1; i++) if (x % i == 0) { ++mr; mp[mr] = i; xc[mr] = 1; while (x % i == 0) { x /= i; xc[mr] = xc[mr] * i; } } if (x != 1) { ++mr; mp[mr] = xc[mr] = x; } } long long get_fct(long long x, long long y) { long long ret = 0; while (x != 0) { ret += (x / y); x /= y; } return ret; } long long cnt_exp(long long x, long long y, long long z) { long long ret = 1; while (y != 0) { if (y % 2 == 1) ret = (ret * x) % z; x = (x * x) % z; y = y >> 1; } return ret; } long long extend_gcd(long long a, long long b, long long &x, long long &y, long long z) { long long i, tmp; if (b == 0) { x = 1; y = 0; return a; } i = extend_gcd(b, a % b, x, y, z); tmp = x; x = y; y = (tmp - a / b * y) % z; return i; } long long CRT() { long long i; long long ret = 0; for (i = 1; i <= mr; i++) { long long x, y; extend_gcd(m / xc[i], xc[i], x, y, xc[i]); x = x % m; ret = (ret + xb[i] * m / xc[i] * x) % m; } return (ret + m) % m; } long long reverse(long long a, long long b) { long long x, y; extend_gcd(a, b, x, y, b); return (x % b + b) % b; } long long cnt_c(long long nn, long long mm) { long long i, j, k; divide_factor(m); for (i = 1; i <= mr; i++) { long long fct_num = get_fct(nn, mp[i]) - get_fct(mm, mp[i]) - get_fct(nn - mm, mp[i]); for (j = 2, circle[1] = 1; j < xc[i]; j++) if (j % mp[i] != 0) circle[j] = (circle[j - 1] * j) % xc[i]; else circle[j] = circle[j - 1]; xb[i] = 1; k = nn; while (k != 0) { xb[i] = (xb[i] * ((cnt_exp(circle[xc[i] - 1], k / xc[i], xc[i]) * circle[k - k / xc[i] * xc[i]]) % xc[i])) % xc[i]; k = k / mp[i]; } for (j = 2, circle[1] = 1; j < xc[i]; j++) { if (j % mp[i] != 0) circle[j] = (circle[j - 1] * reverse(j, xc[i])) % xc[i]; else circle[j] = circle[j - 1]; } k = mm; while (k != 0) { xb[i] = (xb[i] * ((cnt_exp(circle[xc[i] - 1], k / xc[i], xc[i]) * circle[k - k / xc[i] * xc[i]]) % xc[i])) % xc[i]; k = k / mp[i]; } k = nn - mm; while (k != 0) { xb[i] = (xb[i] * ((cnt_exp(circle[xc[i] - 1], k / xc[i], xc[i]) * circle[k - k / xc[i] * xc[i]]) % xc[i])) % xc[i]; k = k / mp[i]; } while (fct_num--) xb[i] = (xb[i] * mp[i]) % xc[i]; } return CRT(); } long long cnt_pos(long long x) { long long i, ret; if (x == 0) return 1; x = x % (2 * m); if (x == 0) x = 2 * m; for (i = 2, ret = 0; i <= x; i++) ret = (ret * i + (i % 2 == 0 ? 1 : -1)) % m; return (ret + m) % m; } int main() { int cas, k; scanf(%d, &cas); for (k = 1; k <= cas; k++) { scanf(%lld%lld%lld, &n, &K, &m); long long ans = cnt_c(n, K); ans = (cnt_pos(n - K) * ans) % m; printf(Case %d: %lld , k, ans); } return 0; }
