文章目錄
-
- 題意
- （beican）曆程
- 正解1
- 正解2
- Code（正解2的）
題意
題目連結
本題大意為 給定m,n
求： P n m P^m_n Pnm的最後一位非0的數
（P在排列組合中就相當于A）
（beican）曆程
看到題目 什麼都不會的我一臉懵
（洛谷的限制太水了
vjudge上時限1s
我們按嚴格的來）
但仔細想了一下 我仍然隻發現暴力是不可以的
我暴力的思路是 乘起來
但直接乘會爆 就留個9位吧（感覺有點靠運氣）
這樣的思路肯定是錯的 （像這位小哥）
也不要想去優化 不然就像我搞了半天 仍然
TLE
接着 再仔細想想 發現求最後一位非0的數 隻需要我們在算的過程中除10
又知道 P n m P^m_n Pnm = n ! ( n − m ) ! \frac{n!}{(n -m)!} (n−m)!n! = ∏ i = n − m + 1 n \prod^n_{i=n-m+1} ∏i=n−m+1ni
換言之我們需要将含有因子2和5的除*掉
BTW将因子2和因子5的數量統計
因為一個10是由一個2和一個5乘得得
直接除*掉不能保證因子2與因子5數量相等
需要把多的乘回去（用快速幂）
for(i = n;i > n - m;i--)
{
int j = i;
while(j % 2 == 0)
{
j /= 2;
d2++;
}
while(j % 5 == 0)
{
j /= 5;
d5++;
}
ans = (ans * j) % 10;
}
if(d2 > d5)
More = qkpow(2,d2 - d5);
else if(d5 > d2) More = qkpow(5,d5 - d2);
整體的代碼大緻如下
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
long long d2,d5,More,ans;
inline long long qkpow(int val,int n)
{
long long rest = 1;
while(n)
{
if(n & 1)
rest = val * rest % 10;
val = val * val % 10;
n >>= 1;
}
return rest;
}
int main()
{
int i,n,m;
while(~scanf("%d%d",&n,&m))
{
d2 = d5 = 0;
More = ans = 1;
for(i = n;i > n - m;i--)
{
int j = i;
while(j % 2 == 0)
{
j /= 2;
d2++;
}
while(j % 5 == 0)
{
j /= 5;
d5++;
}
ans = (ans * j) % 10;
}
if(d2 > d5)
More = qkpow(2,d2 - d5);
else if(d5 > d2) More = qkpow(5,d5 - d2);
printf("%lld\n",ans * More % 10);
}
return 0;
}
**然後又
TLE
**了
然後我不相信我不能成功
又yy出來一個優化版本
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
long long d2,d5,More,ans;
inline long long qkpow(int val,int n)
{
long long rest = 1;
while(n)
{
if(n & 1)
rest = val * rest % 10;
val = val * val % 10;
n >>= 1;
}
return rest;
}
int main()
{
int i,n,m;
while(~scanf("%d%d",&n,&m))
{
if(m == 0)
{
printf("1\n");
continue;
}
d2 = d5 = 0;
More = ans = 1;
for(i = n;i > n - m;i--)
{
int j = i,k;
for(k = 1;!(j & k);k <<= 1,d2++);
j /= k;
while(j % 5 == 0)
{
j /= 5;
d5++;
}
ans = (ans * j) % 10;
}
if(d2 > d5)
More = qkpow(2,d2 - d5);
else if(d5 > d2) More = qkpow(5,d5 - d2);
printf("%lld\n",ans * More % 10);
}
return 0;
}
又
TLE
正解1
其實粗略估一下時間複雜度O（n l o g n log_n lognm）（m為詢問數）
0 <= N<= 20000000
明顯不行 （這題還有點坑，她沒說詢問數上線）
然後我又想了下離線優化（沒YY出來）
最後 我又搞了搞事情 我寫了個預處理
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 20000001;
int d2,d5,More,ans,a[MAXN][3];
inline int qkpow(int val,int n)
{
int rest = 1;
while(n)
{
if(n & 1)
rest = val * rest % 10;
val = val * val % 10;
n >>= 1;
}
return rest;
}
int main()
{
int i,n,m;
for(i = 1;i < MAXN;i++)
if(i % 2 != 0&&i % 5 != 0) a[i][2] = i;
else {
if(i % 2 == 0) a[i][0] = a[i / 2][0] + 1,a[i][2] = a[i / 2][2];
if(i % 5 == 0) a[i][1] = a[i / 5][1] + 1,a[i][2] = a[i / 5][2];
}
a[i][2]存i去掉她的所有2,5因子後的值（如 i = 6 那麼a[i][2] = 3）
a[i][0]存i含的因子2的數量
a[i][1]存i含的因子5的數量
while(~scanf("%d%d",&n,&m))
{
if(m == 0)
{
printf("1\n");
continue;
}
int i,tot = 1,d2,d5;
d2 = d5 = 0;
for(i = n;i > n - m;i--)
{
tot = tot *a[i][2] % 10;
d2 += a[i][0];
d5 += a[i][1];
}
int More = 1;
if(d2 > d5) More = qkpow(2,d2 - d5);
else More = qkpow(5,d5 - d2);
tot = tot * More % 10;
printf("%d\n",tot);
}
return 0;
}
然後慘痛
MLE
(空間超限)（請妳不要用看hen**tai 的眼神看我）
估一下空間
衆所周知 一int占4位元組
1b(byte) = 1 位元組
我用了20000000 * 3 * 4b
即240000kb
但是題目限制65536 kB
阿勒 \color{red}\text{阿勒} 阿勒
我沒超限啊？
不管了 錯了就是錯了 事實如此 無需詭辯
然後去看題解
好多長得一樣的 （我不知道為什麼，真de不知道）
然後寫得一點都不富有親和力
（于是我決定詳詳細細地寫一篇（好像已經很長了））
但是 我們可以考慮用
short int
來存
a[i][2]
隻存i去掉她的所有2,5因子後的值的個位
a[i][0]
存i含的因子2的數量
a[i][1]
存i含的因子5的數量
a[i][0] 可以 與 a[i][1]相等部分可以抵消（是以a[i][0] 和 a[i][1]中始終有一個是0）
易發現
2 1 2^1 21 = 2 2 2 2^2 22 = 4 2 3 2^3 23 = 8 2 4 = 6 2^4 = 6 24=6 2 5 = 2 2^5 = 2 25=2
以上都是mod 10後的 可以發現有循環産生
5也有相同情景 就可以采用某種神奇的存儲方式
達到用short int存的效果
這裡就點到為止 不再展開（感興趣的同學可以向這個方向想一下）
我是沒有想出來的
妳才沒有被坑
讓我們把精力放在真正的正解上（滑稽
正解2
思路不變仍然要統計2,5的個數
不過不枚舉 直接從整個階乘去求
inline int kiyo(int n,int div)
{
if(n == 0) return 0;
return (n / div + kiyo(n / div,div));
}
div為求的數
如 求 5!中含因子2的個數
就
kiyo(5,2)
return 0;
很好了解
但 為什麼
return (n / div + kiyo(n / div,div));
n / div 是針對1~n的含div的個數
但考慮到 kiyo(5,2) 中有4這種情況
4中有兩個2但n / div隻統計了一次
kiyo(n / div,div)
就是為了統計未統計到的
舉個栗子
kiyo(10,2)
1 2 3 4 5 6 7 8 9 10
0 1 0 1 0 1 0 1 0 1第一次
n / div
1 2 3 4 5第二次
n / div
0 1 0 1
但由于第二次是除了一次2的
是以實際算的是
2 4 6 8 10
0 1 0 1 0
類似的
最終可得
1 2 3 4 5 6 7 8 9 10
0 1 0 2 0 1 0 3 0 1 8
再用
kiyo(n,div)
-
kiyo(n - m,div)
在logn的時間複雜度内求出2,5的個數
也許有同學會想到 那麼再求出3,7的個數就行了啊
因為 偶數都可以轉化為對應的奇數
而 1 3 5 7 9中
1不管
9是3的倍數
5已經求了
把7,3求一下
OK!
然後 妳 就 華麗地爆零 瞬間成為奧林匹斯山上的宙斯
Why?
因為 13 17 等雖不是3,7的倍數 卻有3,7
是以 求的應該是末位是3,7,9的的數的個數
以下即為求法
get(a,b)
即求1~a中有多少末位為b的
inline int odd(int n,int div)
{
if(n == 0) return 0;
return n / 10 + (n % 10 >= div) + odd(n / 5,div);
按以下分步的
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
....
n+1 n+2...
是以是先 n / 10 代表有幾層就有幾個末位是div的
但考慮到可能n是10a+b（b<10）的形式就有可能還有1個
是以(n % 10 >= div)
但以上沒有考慮5
如15/5=3
而除以5的操作是之前進行的 這裡沒有記錄15仍然是15
是以還需 odd(n / 5,div)跟上面kiyo含意類似
類似地 同學可能會說6不是還要除以2嗎 為什麼不再調用一個odd(n / 2,div)
因為get()已經解決了該問題
}
inline int get(int n,int div)
{
if(n == 0) return 0;
return (get(n / 2,div) + odd(n,div));
分成奇偶兩個數列
因為算的都是1~n
是以隻有兩種情況
Case1:n ≡ 0 (mod 2)
可以分為
1 3 5...n-1
這邊（上面）的就可以調odd()函數算了
為什麼odd()的不除以2呢？ 因為odd()預設算奇數
2 4 6...n
進行除2操作類似于odd的除5操作
Case2:n ≡ 1 (mod 2)
1 3 5...n
2 4 6...n-1
其實與Case1差不多int a = b / 2;
b為奇的話 就相當于(b-1)/2
不影響get(n / 2,div)
odd(n,div)直接傳的n多的那一位也有考慮在内
}
由此可以得到含因子2,5的數量
和1~n中末位為3,7,9的數量
還需
因為求的是 P n m P^m_n Pnm = n ! ( n − m ) ! \frac{n!}{(n -m)!} (n−m)!n! = ∏ i = n − m + 1 n \prod^n_{i=n-m+1} ∏i=n−m+1ni
Code（正解2的）
#include <cstdio>
#include <vector>
using namespace std;
inline int qkpow(int val,int n)
{
int rest = 1;
while(n)
{
if(n & 1)
rest = val * rest % 10;
val = val * val % 10;
n >>= 1;
}
return rest;
}
inline int kiyo(int n,int div)
{
if(n == 0) return 0;
return (n / div + kiyo(n / div,div));
}
inline int odd(int n,int div)
{
if(n == 0) return 0;
return n / 10 + (n % 10 >= div) + odd(n / 5,div);
}
inline int get(int n,int div)
{
if(n == 0) return 0;
return (get(n / 2,div) + odd(n,div));
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
無限輸入
int ans = 1;
int t2 = kiyo(n,2) - kiyo(n - m,2);
int t5 = kiyo(n,5) - kiyo(n - m,5);
計算含2,5因子數
int t3 = get(n,3) - get(n - m,3);
int t7 = get(n,7) - get(n - m,7);
int t9 = get(n,9) - get(n - m,9);
算末位為3,7,9的數的個數
if(t2 > t5) ans = ans * qkpow(2,t2 - t5) % 10;
else ans = ans * qkpow(2,t5 - t2) % 10;
ans = ans * qkpow(3,t3) % 10;
ans = ans * qkpow(7,t7) % 10;
ans = ans * qkpow(9,t9) % 10;
套快速幂 logn
好像在這裡還有O（1）的做法 不太懂 感興趣的同學可以去看看其它部落格
printf("%d\n",ans);
}
return 0;
}
恭喜妳
又能AC一題
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)