递归规范写法（P1762 偶数）
打表（杨辉三角一般都是规律题）
#include<bits/stdc++.h>
using namespace std;
int n;
int f[102][102];
int main(){
f[0][0]=1;
for(int i=1;i<=50;++i){
//cout << i << ": ";
printf("%3d: ",i);
for(int j=1;j<=i;++j){
f[i][j]=f[i-1][j]+f[i-1][j-1];
if(f[i][j]%2) cout << "*";
else cout << '.';
}
cout << "\n";
}
return 0;
}
==> f(2k + t)= 3k + 2* f ( t )
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const mod=1000003;
ll ksm(ll a,ll b){
ll res=1;
while(b){
if(b&1) (res*=a)%=mod;
b >>= 1;
a*=a;
a%=mod;
}
return res;
}
int v[57];
ll v2[57],ans,sum;
int f(ll& n){
if(n==1) return 1;
ll k=log(n)/log(2);
n-=v2[k];
ll res=0;
res+=v[k];
if(n) res+=2*f(n); //if优秀的剪枝
if(res>mod) {
res-=res/mod*mod;
}
return res;
}
ll n;
int main(){
cin >> n;
v[0]=1;v2[0]=1;
for(int i=1;i<=52;++i){
v[i]=v[i-1]*3%mod;
v2[i]=v2[i-1]*2;
}
ll z=n%mod;
ans=(z+1)* ksm(2,mod-2)%mod*z%mod;
ans-=f(n);
ans=(ans%mod+mod)%mod;
cout << ans;
return 0;
}
查看7道真题和解析