HDNOIP201405楊輝三角，hdnoip201405楊輝
2016.1.27
試題描述
楊輝三角是形如如下的數字三角形：
1
1 1
1 2 1
……
現在想求出楊輝三角第N行的N個數中，有多少個數能被給定的質數p整除。
輸入
一行兩個空格隔開的整數N和p
輸出
輸出一個整數，表示第N行能被給定的質數p整除的個數
輸入示例
3 2
輸出示例
1
其他說明
對於60%的數據，N≤30，p≤1000，對於80%的數據，N≤1000，p≤1000，對於100%的數據，N≤〖10〗^9，p≤1000
首先知道是盧卡斯定理 和 組合數取模
然後就一個一個試呗
![]()
#include<iostream>
using namespace std;
int a[1005],e,ans;
int main()
{
int n,p,b,ct;
scanf("%d%d",&n,&p);
b=n-=1;
while(b)
{
a[++e]=b%p;
b/=p;
}
for(int i=0;i<=n;i++)
{
b=i;ct=1;
while(b)
{
if(b%p>a[ct]) {ans+=1;break;}
else {ct++;b/=p;}
}
}
printf("%d",ans);
}
View Code
然後果斷TLE
然後根據楊輝三角的對稱性，砍一半
![]()
#include<iostream>
using namespace std;
int a[1005],e,ans;
int main()
{
int n,p,b,ct;
scanf("%d%d",&n,&p);
b=n-=1;
while(b)
{
a[++e]=b%p;
b/=p;
}
for(int i=0;i<(n+1)/2;i++)
{
b=i;ct=1;
while(b)
{
if(b%p>a[ct]) {ans+=1;break;}
else {ct++;b/=p;}
}
}
ans*=2;
if(n+1&1)
{
b=n/2;ct=1;
while(b)
{
if(b%p>a[ct]) {ans+=1;break;}
else {ct++;b/=p;}
}
}
printf("%d",ans);
}
View Code
然並卵，依舊TLE
於是機智的我想到了構造
還想到了狀態壓縮
就是二進制某一位為1表示構造的數在p進制下該位上比n在對應位上大
![]()
#include<iostream>
using namespace std;
int a[105],e,ans;
int main()
{
int n,p,b,ct;
scanf("%d%d",&n,&p);
b=n-=1;
while(b)
{
a[++e]=b%p;
b/=p;
}
for(int t = e-1 ; t >= 1 ; t-- )
{
for(int i = ( 1 << t ) - 1 ; i >= 1 ; i-- )
{
b=i;ct=a[t+1];
for(int j = t-1 ; j >= 0; j-- )
{
if(1<<j&b) ct*=p-1-a[j+1];
else ct*=a[j+1]+1;
}
ans+=ct;
}
}
printf("%d",ans);
}
View Code
AC後激動的我瞬間覺得我有做神犇的潛質
但我發現其他人的代碼都特短。。。
我方了
冷靜後，發現我傻*了
明明可以反著算。。。要知道根據盧卡斯定理構造模p不等於0的數有多簡單。。。
看了代碼瞬間就懂的
AC代碼：
![]()
#include<iostream>
using namespace std;
int e,ans=1;
int main()
{
int n,p,b;
scanf("%d%d",&n,&p);
b=n-1;
while(b)
{
ans*=b%p+1;
b/=p;
}
printf("%d",n-ans);
}
View Code
