「オイラープロジェクト241～250」の編集履歴（バックアップ）一覧に戻る
*問い249
S = {2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする。
要素の合計が素数となるような、S の部分集合の数を求めよ。
最下位の 16 桁を答えとして入力せよ。
メモ化計算で計算量を落としますが、かなり遅いです。
一応数分で答えが出ますが、一分ルール切れてません。
#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
const int up=1600000;
std::vector<int> sosuu;
bool so[up+1];
__int64 memo[up+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
for(int i=0;i<=up;i+=2)so[i]=false;
so[1]=false;
so[2]=true;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
int main(){
setSo();//素数の集合を求める
int area=0,p;
__int64 ten=1,ans=0;
for(int i=0;i<16;i++){
ten*=10;
}
memset(memo,0,sizeof(memo));
memo[0]=1;
for(int i=0;sosuu[i]<5000;i++){
p=sosuu[i];//メモ化というか動的計画法というかそんな感じで組み合わせ数を計算
for(int j=area;j>=0;j--){
memo[j+p]=(memo[j+p]+memo[j])%ten;
}
area+=p;
}
printf("%d\n",area);
for(int i=2;i<=area;i++){
if(so[i]==true)ans=(ans+memo[i])%ten;//集計
//std::cout<<i<<" "<<memo[i]<<"\n";
}
std::cout<<ans<<"\n"<<ans-memo[area]*so[area];
}
*問い250
要素の合計が 250 で割り切れるような、{1^1, 2^2, 3^3,..., 250250^250250} の空でない部分集合の数を求めよ。最下位の 16 桁を答えとして入力せよ。
modの範囲が狭いことを利用して解きます。
これも249と同じく動的計画法というか一回ずつのメモ化計算で片が付きます。
mod計算は早いと思い込んでましたが引き算より圧倒的に遅いのですね。
桁あふれを防ぐための計算を
if(memo[next][p]>=ten)memo[next][p]-=ten;
としたらかなり速度が上がりました。
#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
const int mod=250;
int calc(int n){
int m=n,ans=1;
n%=mod;
while(m!=0){
if(m%2==1){
ans=(ans*n)%mod;
}
n=(n*n)%mod;
m/=2;
}
return ans;
}
int main(){
//1425480602091519
__int64 ten=1;
for(int i=0;i<16;i++){
ten*=10;
}
__int64 memo[2][mod+1];
memset(memo,0,sizeof(memo));
int now,next,u;
//memo[0][0]=1;
for(int i=1;i<=250250;i++){
now=(i+1)%2;
next=i%2;
u=calc(i);
memcpy(memo[next],memo[now],sizeof(memo[next]));
int p;
for(int j=0;j<mod;j++){
p=(j+u)%mod;
memo[next][p]+=memo[now][j];
if(memo[next][p]>=ten)memo[next][p]-=ten;
}
memo[next][u]=(memo[next][u]+1)%ten;//このiが部分集合の初めの場合を足す
}
std::cout<<memo[next][0]<<"\n";
}
