(fht.cpp/c/pas)
荷葉葉是一位偉大的數♂學家。 荷葉葉發明了一個函數，并稱之為快速荷葉葉變換（Fast H10 Transfrom）
但荷葉葉比較懶，對于函數的計算，荷葉葉把這個任務交給了你。 由于答案可能會很大，請輸出答案對1000000007取模的值。
一行，包含兩個整數N，M。
1個整數，FHT(N,M) mod 1000000007的值。
| fht.in | fht.out |
|---|---|
| 3 4 | 1 |
對于 40% 的數據，1 ≤ N，M ≤ 1000 對于 60% 的數據，1 ≤ N，M ≤ 10 6
對于 100% 的數據，1 ≤ N，M ≤ 10 9
從小到大枚舉i發現
i = n … n/2 + 1 時， n mod i = 0, 1, 2, 3, 4, …;i = n/2 … n/3 + 1時， n mod i= n mod (n/2), n mod (n/2) + 2, n mod (n/2) + 4, ……(請讀者自己試試）剩下的最后一小段枚舉即可。
代碼#include <cstdio>#include <cstdlib>using namespace std;const long long mod = 1000000007;long long n, m;inline long long sum(long long s, long long tot, long long c){ return (s + s + (tot - 1) * c % mod) % mod * tot >> 1 % mod;}inline long long solve(long long n) //求出∑i = 1..n n % i { register long long i = 2, l = 0, r = n + 1; long long ans = 0; do { l = r - 1; r = n / i + 1; (ans += sum(n % l, l - r + 1, i - 1)) %= mod; i++; }while(n / (i - 1) - n / i> 1); for(i = 1; i <= r - 1; i++) (ans += n % i) %= mod; return ans;}int main(){ freopen("fht.in", "r", stdin); freopen("fht.out", "w", stdout); long long sum; scanf("%lld%lld", &n, &m); sum = solve(n) * solve(m) % mod; 幻象(phantom.cpp/c/pas)
phantom是一位愛思考的哲♂學家。 最近phantom得到了森の妖精的真傳。在他練功的時候, 每秒他的思緒中 都有一定的概率浮現出奇♂異的幻象,持續x秒的幻象將產生x 2 的幻象值。 phantom練功發自真心,他想知道,在N秒內他期望產生的幻象值是多少。
第一行包含 1 個正整數 N ，表示總時間 N 秒。 第二行包含 N 個用空格隔開的在[0,100]之間的正整數，其中第i個數a[i] 表示第i秒浮現幻象的概率為百分之a[i]。
1 個實數，四舍五入后保留一位小數，表示期望幻象值。
| phantom.in | phantom.out |
|---|---|
| 3 | 1 |
| 50 50 50 |
【數據規模與約定】 對于 40%的數據 N ≤ 10 對于 60%的數據 N ≤ 100 對于 100%的數據，N ≤ 10 ^ 6 數據規模較大，請使用效率較高的讀入方式。
設L[i]為第i秒幻象的持續時間的期望. 顯然L[i] = (L[i-1] + 1) * a[i]% 設f[i]表示前i秒的答案 f[i] = f[i-1] + ((L[i-1] + 1) ^ 2 – L[i-1] ^ 2) * a[i]% 時間復雜度為O(N)
#include <cstdio>#include <cstdlib>using namespace std;const int maxn = 800005;double f[maxn], l[maxn], a[maxn];int n;inline double pow(double x){ return x * x;}int main(){ freopen("phantom.in", "r", stdin); freopen("phantom.out", "w", stdout); register int i, k; scanf("%d", &n); for(i = 1; i <= n; i++) { scanf("%d", &k); a[i] = k / 100.; l[i] = (l[i - 1] + 1) * a[i]; } for(i = 1; i <= n; i++) f[i] = f[i - 1] + (pow(l[i - 1] + 1) - pow(l[i - 1])) * a[i]; printf("%.1lf", f[n]); return 0;}（sherco.cpp/c/pas)
Sherco是一位經驗豐富的魔♂法師。 Sherco在第零次圣杯戰爭中取得了勝利,并取得了王之寶藏——王の樹。 他想把這棵樹砍去任意條邊，拆成若干棵新樹，并裝飾在他的摩托上，讓他 的摩托更加酷炫。 但Sherco認為，這樣生成的樹不具有美感，于是Sherco想讓每棵新樹的節 點數相同。 他想知道有多少種方法分割這棵樹。
第一行一個正整數N，表示這棵樹的結點總數。 接下來N-1行，每行兩個數字X，Y表示編號為X的結點與編號為Y的結點 相連。結點編號的范圍為[1,N]。
一個整數，表示方案數。注意，不砍去任何一條邊也算作一種方案。
【輸入輸出樣例】
| sherco.in | sherco.out |
|---|---|
| 6 | 3 |
| 1 2 | |
| 2 3 | |
| 2 4 | |
| 4 5 | |
| 5 6 |
對于40%的數據，N ≤ 15 對于60%的數據，N ≤ 10^5 對于100%的數據，N ≤ 10^6 數據規模非常大，請使用高效的讀入方式。
暴力枚舉刪哪些邊,期望得分40分。 觀察到一些性質： 1.樹的大小只可能是N的約數 2.樹的大小確定的話，方案最多只有一種 我們可以枚舉樹的大小,并DFS判定是否可行。 時間復雜度O（n√n），期望得分60分。 繼續觀察到一些性質： 將原樹看做一個有根樹，一個節點可以作一個塊的”根”， 當且僅當該節點的size能被塊的大小整除 預處理出每個節點的size,枚舉樹的大小k,判斷size為k的 倍數的節點數量是否為N/k。 時間復雜度O(NlnN)
#include <cstdio>#include <cstdlib>using namespace std;const int maxn = (int)1e6 + 5;struct edge { int to, next;}e[maxn * 2];struct point { int root, fa;};int n, ans, tot;int h[maxn], size[maxn], p[maxn];inline int read(){ char c; do { c = getchar(); }while(c < '0' || c > '9'); int sum = 0; do { (sum *= 10) += c - 48; c = getchar(); }while('0' <= c && c <= '9'); return sum;}inline void add(int u, int v){ tot++; e[tot] = (edge) {v, h[u]}; h[u] = tot;}void dfs(const point &s){ int i; size[s.root] = 1; for(i = h[s.root]; i; i = e[i].next) if(e[i].to != s.fa) { dfs((point){e[i].to, s.root}); size[s.root] += size[e[i].to]; } p[size[s.root]]++;}int main(){ freopen("sherco.in", "r", stdin); freopen("sherco.out", "w", stdout); int i, j, u, v; n = read(); for(i = 1; i < n; i++) { u = read(); v = read(); add(u, v); add(v, u); } dfs((point){1, 0}); for(i = 1; i <= n; i++) { int sum = p[i]; for(j = 2 * i; j <= n; j += i) sum += p[j]; if(sum * i == n) ans++; } printf("%d/n", ans); return 0;}新聞熱點
疑難解答
